The Library
Parallel algorithm for the matrix chain product problem
Tools
Tools
Tools
Czumaj, Artur (1992) Parallel algorithm for the matrix chain product problem. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)
|
PDF (Department of Computer Science Research Report)
WRAP_cs-rr-225.pdf - Other - Requires a PDF viewer. Download (1557Kb) | Preview |
Abstract
This paper considers the problem of finding an optimal order of the multiplication chain of matrices. All parallel algorithms known use the dynamic programming approach and run in a polylogarithmic time using, in the best case, n6/log6n processors. Our algorithm uses a different approach and reduces the problem to computing some recurrence on a tree. We show that this recurrence can be optimally solved which enables us to improve the parallel bound by a few factors. Our algorithm runs in O (log3n) time using n2/log3n processors on a CREW PRAM and O(log2n log log n) time using n2/(log2n log log n)processors on a CRCW PRAM. This algorithm solves also the problem of finding an optimal triangulation in a convex polygon. We show that for a monotone polygon this result can be even improved to get an O(log2n) time and n processor algorithm on a CREW PRAM.
| 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 algorithms | ||||
| Series Name: | Department of Computer Science research report | ||||
| Publisher: | University of Warwick. Department of Computer Science | ||||
| Official Date: | June 1992 | ||||
| Dates: |
|
||||
| Number: | Number 225 | ||||
| Number of Pages: | 19 | ||||
| DOI: | CS-RR-225 | ||||
| Institution: | University of Warwick | ||||
| Theses Department: | Department of Computer Science | ||||
| Status: | Not Peer Reviewed | ||||
| Publication Status: | Unpublished | ||||
| Funder: | Komitet BadanĚ Naukowych (Poland) (KBN) | ||||
| 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
