The Library
An optimal parallel algorithm for computing a nearoptimal order of matrix multiplications
Tools
Czumaj, Artur (1992) An optimal parallel algorithm for computing a nearoptimal order of matrix multiplications. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)

PDF (Department of Computer Science Research Report)
WRAP_csrr224.pdf  Other  Requires a PDF viewer. Download (6Mb)  Preview 
Abstract
This paper considers the computation of matrix chain products of the form M1 x M2 x ... M(n1). 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 (log2n) time using n6/log6n processors. This paper presents the first approximating optimal parallel algorithm for this problem and for the problem of finding a nearoptimal 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.
Item Type:  Report  

Subjects:  Q Science > QA Mathematics  
Divisions:  Faculty of Science, Engineering and Medicine > Science > Computer Science  
Library of Congress Subject Headings (LCSH):  Matrices, Parallel processing (Electronic computers)  
Series Name:  Department of Computer Science research report  
Publisher:  University of Warwick. Department of Computer Science  
Official Date:  February 1992  
Dates: 


Number:  Number 224  
Number of Pages:  18  
DOI:  CSRR224  
Institution:  University of Warwick  
Theses Department:  Department of Computer Science  
Status:  Not Peer Reviewed  
Publication Status:  Unpublished  
Reuse Statement (publisher, data, author rights):  A. Czumaj, “An Optimal Parallel Algorithm for Computing a NearOptimal Order of Matrix Multiplications”, <i>Algorithm Theory</i>, Lecture Notes in Computer Science 621, ed. O. Nurmi and E. Ukkonen, SpringerVerlag, Berlin, pp. 6272 (1992); Proceedings of the 3rd Scandinavian Workshop on Algorithm Theory, Helsinki, July 1992 (SWAT '92)  
Grant number:  KBN 211909101  
Related URLs: 
Request changes or add full text files to a record
Repository staff actions (login required)
View Item 
Downloads
Downloads per month over past year