Efficient matrix chain ordering in polylog time

Philip G. Bradford; Gregory J.E. Rawlins; Gregory E. Shannon

Efficient matrix chain ordering in polylog time

Philip G. Bradford
, Gregory J.E. Rawlins
, Gregory E. Shannon

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

4 Scopus citations

Abstract

This paper gives an O(lg³n)-time and n/lgn processor algorithm for solving the matrix chain ordering problem and for finding optimal triangulations of a convex polygon on the Common CRCW PRAM model. This algorithm works by finding shortest paths in special digraphs modeling dynamic programming tables. Also, a key part of the algorithm is improved by computing row minima of a totally monotone matrix, this lets the algorithm run in O(lg²n) time with n processors on the EREW PRAM or even O(log²n lglg n) time with n/lglgn processors on the CRCW PRAM.

Original language	English
Title of host publication	Proceedings of the International Conference on Parallel Processing
Publisher	Publ by IEEE
Pages	234-241
Number of pages	8
ISBN (Print)	0818656026
State	Published - 1994
Externally published	Yes
Event	Proceedings of the 8th International Parallel Processing Symposium - Cancun, Mex Duration: Apr 26 1994 → Apr 29 1994

Publication series

Name	Proceedings of the International Conference on Parallel Processing
ISSN (Print)	0190-3918

Conference

Conference	Proceedings of the 8th International Parallel Processing Symposium
City	Cancun, Mex
Period	04/26/94 → 04/29/94

Cite this

@inproceedings{40c794bb8a82491a9aa52271a665b207,

title = "Efficient matrix chain ordering in polylog time",

abstract = "This paper gives an O(lg3n)-time and n/lgn processor algorithm for solving the matrix chain ordering problem and for finding optimal triangulations of a convex polygon on the Common CRCW PRAM model. This algorithm works by finding shortest paths in special digraphs modeling dynamic programming tables. Also, a key part of the algorithm is improved by computing row minima of a totally monotone matrix, this lets the algorithm run in O(lg2n) time with n processors on the EREW PRAM or even O(log2n lglg n) time with n/lglgn processors on the CRCW PRAM.",

author = "Bradford, \{Philip G.\} and Rawlins, \{Gregory J.E.\} and Shannon, \{Gregory E.\}",

year = "1994",

language = "English",

isbn = "0818656026",

series = "Proceedings of the International Conference on Parallel Processing",

publisher = "Publ by IEEE",

pages = "234--241",

booktitle = "Proceedings of the International Conference on Parallel Processing",

note = "Proceedings of the 8th International Parallel Processing Symposium ; Conference date: 26-04-1994 Through 29-04-1994",

}

Efficient matrix chain ordering in polylog time. / Bradford, Philip G.; Rawlins, Gregory J.E.; Shannon, Gregory E.
Proceedings of the International Conference on Parallel Processing. Publ by IEEE, 1994. p. 234-241 (Proceedings of the International Conference on Parallel Processing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Efficient matrix chain ordering in polylog time

AU - Bradford, Philip G.

AU - Rawlins, Gregory J.E.

AU - Shannon, Gregory E.

PY - 1994

Y1 - 1994

N2 - This paper gives an O(lg3n)-time and n/lgn processor algorithm for solving the matrix chain ordering problem and for finding optimal triangulations of a convex polygon on the Common CRCW PRAM model. This algorithm works by finding shortest paths in special digraphs modeling dynamic programming tables. Also, a key part of the algorithm is improved by computing row minima of a totally monotone matrix, this lets the algorithm run in O(lg2n) time with n processors on the EREW PRAM or even O(log2n lglg n) time with n/lglgn processors on the CRCW PRAM.

AB - This paper gives an O(lg3n)-time and n/lgn processor algorithm for solving the matrix chain ordering problem and for finding optimal triangulations of a convex polygon on the Common CRCW PRAM model. This algorithm works by finding shortest paths in special digraphs modeling dynamic programming tables. Also, a key part of the algorithm is improved by computing row minima of a totally monotone matrix, this lets the algorithm run in O(lg2n) time with n processors on the EREW PRAM or even O(log2n lglg n) time with n/lglgn processors on the CRCW PRAM.

UR - https://www.scopus.com/pages/publications/0027928998

M3 - Conference contribution

AN - SCOPUS:0027928998

SN - 0818656026

T3 - Proceedings of the International Conference on Parallel Processing

SP - 234

EP - 241

BT - Proceedings of the International Conference on Parallel Processing

PB - Publ by IEEE

T2 - Proceedings of the 8th International Parallel Processing Symposium

Y2 - 26 April 1994 through 29 April 1994

ER -

Efficient matrix chain ordering in polylog time

Abstract

Publication series

Conference

Other files and links

Fingerprint

Cite this