The Library
An optimal parallel algorithm for computing a near-optimal order of matrix multiplications
Tools
Tools
Tools
Czumaj, Artur (1992) An optimal parallel algorithm for computing a near-optimal 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_cs-rr-224.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(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 (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 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.
| 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: | CS-RR-224 | ||||
| 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 Near-Optimal Order of Matrix Multiplications”, <i>Algorithm Theory</i>, 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) | ||||
| Grant number: | KBN 2-11-90-91-01 | ||||
| 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
