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)

Preview

PDF (Department of Computer Science Research Report) WRAP_cs-rr-225.pdf - Other - Requires a PDF viewer. Download (1557Kb) | Preview

Request Changes to record.

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 > 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:	Date Event June 1992 Completion
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 Badań Naukowych (Poland) (KBN)
Grant number:	KBN 2-11-90-91-01
Related URLs:	Organisation

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads