<%@ page language="java" contentType="text/html" %> <%-- Include common initialisation code --%> <%@ include file="/arch/common.jsp" %> <%-- The current tab --%> <% String currentTab = "Research"; %> <%-- Content of navigation pane --%> <%@ include file="nav.jsp" %> <% showCurrentLink=true; %> <%-- Current navigation location --%> <% String currentNav = "Reports and Theses"; %> <%-- Include the code for the document header --%> <%@ include file="/arch/header.jsp" %>

Research Report CS-RR-224

<%-- Include the code for the lines and navigation --%> <%@ include file="/arch/middle.jsp" %>

Artur Czumaj, An Optimal Parallel Algorithm for Computing a Near-Optimal Order of Matrix Multiplications (February 1, 1992).

Abstract

This paper considers the computation of matrix chain products of the form M1 x M2 x ... M(n-1). The order in which the matrices are multiplied affects the number of operations. The best sequential algorithm for computing an optimal order of matrix multiplication runs in O (n log n) time while the best known parallel NC algorithm runs in O (log² n) time using n⁶/log⁶ n processors. This paper presents the first approximating optimal parallel algorithm for this problem and for the problem of finding a near-optimal triangulation of a convex polygon. The algorithm runs in O (log n) time using n /logn processors on a CREW PRAM, and O ( log log n) time using n / log log n processors on a weak CRCW PRAM. It produces an order of matrix multiplications and a partition of polygon which differ from the optimal ones at most 0.1547 times.

<%@ include file="cited.html" %>

A. Czumaj, "An Optimal Parallel Algorithm for Computing a Near-Optimal Order of Matrix Multiplications", Algorithm Theory, Lecture Notes in Computer Science 621, ed. O. Nurmi and E. Ukkonen, Springer-Verlag, Berlin, pp. 62-72 (1992); Proceedings of the 3rd Scandinavian Workshop on Algorithm Theory, Helsinki, July 1992 (SWAT '92)

<%-- Include the code for the document footer --%> <%@ include file="/arch/footer.jsp" %>