Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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)

[img]
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, 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:
DateEvent
June 1992Completion
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 View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us