{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:37:50Z","timestamp":1787337470048,"version":"build-2736575974"},"reference-count":45,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>The matrix chain ordering problem is to find the cheapest way to multiply a chain of n matrices, where the matrices are pairwise compatible but of varying dimensions. Here we give several new parallel algorithms including $O(\\lg^3 n)$-time and $n\/\\!\\lg n$-processor algorithms for solving the matrix chain ordering problem and for solving an optimal triangulation problem of convex polygons on the common CRCW PRAM model. Next, by using efficient algorithms for computing row minima of totally monotone matrices, this complexity is improved to $O(\\lg^2 n)$ time with n processors on the EREW PRAM and to $O(\\lg^2 n \\lg \\lg n)$ time with $n\/ \\! \\lg \\lg n$ processors on a common CRCW PRAM\\@. A new algorithm for computing the row minima of totally monotone matrices improves our parallel MCOP algorithm to $O(n \\lg^{1.5} n)$work and polylog time on a CREW PRAM\\@. Optimal log-time algorithms for computing row minima of totally monotone matrices will improve our algorithm and enable it to have the same work as the sequential algorithm of Hu and Shing [SIAM J. Comput., 11 (1982), pp. 362--373; SIAM J. Comput., 13 (1984), pp. 228--251].<\/jats:p>","DOI":"10.1137\/s0097539794270698","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"466-490","source":"Crossref","is-referenced-by-count":13,"title":["Efficient Matrix Chain Ordering in Polylog Time"],"prefix":"10.1137","volume":"27","author":[{"given":"Phillip G.","family":"Bradford","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gregory J. E.","family":"Rawlins","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gregory E.","family":"Shannon","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840359"},{"key":"R2","unstructured":"A. Aggarwal and J. Park,\n                      Parallel searching multidimensional monotone arrays\n                      , J. Algorithms, to appear, and 29th FOCS, 1988, pp. 497\u2013512."},{"key":"R3","unstructured":"A. Aho, D\u017e. Hopkroft, D\u017e. Ul\u2019man, Postroenie i analiz vychislitelnykh algoritmov, \u201cMir\u201d, 1979, 536\u20130, Translated by A. O. Slisenko; Edited by Ju. V. Matijasevi\u010d80g:68036"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90105-0"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/0219066"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(92)90046-F"},{"key":"R7","unstructured":"M. J. Atallah, S. R. Kosaraju, L. L. Larmore, G. L. Miller, and S.\u2010H. Teng,\n                      Constructing Trees in Parallel\n                      , Proc. 1st Symp. on Parallel Algorithms and Architectures, 1989, pp. 499\u2013533."},{"key":"R8","unstructured":"O. Berkman, D. Breslauer, Z. Galil, B. Schieber, and U. Vishkin,\n                      Highly parallelizable problems\n                      , Symposium on the theory on computing, 1989, pp. 309\u2013319."},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1993.1018"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/0898-1221(95)00138-O"},{"key":"R11","unstructured":"P. G. Bradford,\n                      Efficient Parallel Dynamic Programming\n                      , Extended Abstract in the Proceedings of the 30th Allerton Conference on Communication, Control and Computation, University of Illinois at Urbana\u2010Champaign, 1992, pp. 185\u2013194. Full version: Technical Report #352, Indiana University, April 1992 and October 1994 (revised)."},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/0898-1221(95)00138-O"},{"key":"R13","unstructured":"P. G. Bradford, V. Choppella, and G. J. E. Rawlins,\n                      Lower bounds for the matrix chain ordering problem (extended abstract)\n                      , in the Proceedings of LATIN \u201995: Theoretical Informatics, R. Baeza\u2010Yates, E. Goles, and P. V. Poblete, eds., Lecture Notes in Computer Science # 911, Springer\u2010Verlag, 1995, pp. 112\u2013130. Full version to be submitted shortly."},{"key":"R14","unstructured":"P. G. Bradford, R. Fleischer, and M. Smid,\n                      A Polylog\u2010Time and O(nlgn)\u2010Work Parallel Algorithm for Finding the Row Minima in Totally Monotone Matrices\n                      , Max\u2010Planck\u2010Institut f\u00fcr Computer Science Technical Report: MPI\u2013I\u201395\u20131\u2013006, Saarbr\u00fccken, Germany, March 1995, submitted."},{"key":"R15","unstructured":"P. G. Bradford, G. J. E. Rawlins, and G. E. Shannon,\n                      Matrix Chain Ordering in Polylog Time with n\/lgn Processors\n                      , Technical Report # 360, Indiana University, December 1992."},{"key":"R16","unstructured":"D. Z. Chen,\n                      Efficient geometric algorithms on the EREW PRAM\n                      ,\n                      Proceedings of the 28th Allerton Conference on Communication, Control, and Computation\n                      , Monticello, IL, 1990, pp. 818\u2013827."},{"key":"R16","unstructured":"Full version in\n                      IEEE Trans. on Parallel and Distributed Systems\n                      , 6 (1995), pp. 41\u201347."},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1145\/359545.359556"},{"key":"R18","volume-title":"Introduction to algorithms","author":"Manber Udi","year":"1989"},{"key":"R19","unstructured":"Artur Czumaj, An optimal parallel algorithm for computing a near\u2010optimal order of matrix multiplications, Lecture Notes in Comput. Sci., Vol. 621, Springer, Berlin, 1992, 62\u2013721249493"},{"key":"R20","unstructured":"A. Czumaj,\n                      Parallel algorithm for the matrix chain product and the optimal triangulation problem\n                      , STACS 93, Springer Verlag, LNCS # 665, 1993, pp. 294\u2013305."},{"key":"R21","unstructured":"L. E. Deimel, Jr. and T. A. Lampe,\n                      An Invariance Theorem Concerning Optimal Computation of Matrix Chain Products\n                      , North Carolina State Univ., Technical Report # TR79\u201014."},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(99)00098-8"},{"key":"R23","first-page":"404","volume":"34","author":"Ma Jun","year":"1999","journal-title":"Shandong Daxue Xuebao Ziran Kexue Ban"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1145\/7902.7903"},{"key":"R25","unstructured":"S.\u2010H. S. Huang, H. Liu, and V. Viswanathan,\n                      Parallel dynamic programming\n                      , Proc. 2nd IEEE Symposium on Parallel and Distributed Processing, 1990, pp. 497\u2013500."},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90258-H"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(81)90014-6"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1137\/0211028"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1137\/0213017"},{"key":"R30","unstructured":"O. H. Ibarra, T.\u2010C. Pong, and S. M. Sohn,\n                      Hypercube Algorithms for Some String Comparison Problems\n                      , Proc. IEEE International Conference on Parallel Processing, 1988, pp. 190\u2010193."},{"key":"R31","unstructured":"J. J\u00e1J\u00e1,\n                      An Introduction to Parallel Algorithms\n                      , Addison\u2010Wesley, 1992."},{"key":"R32","unstructured":"D. G. Kirkpatrick and T. Przytycka,\n                      Parallel Construction of Near Optimal Binary Search Trees\n                      , Proc. Symposium on Parallel Algorithms and Architectures, 1990, pp. 234\u2013243."},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1137\/0218014"},{"key":"R34","unstructured":"S. K. Kim,\n                      Optimal Parallel Algorithms on Sorted Intervals\n                      , TR 90\u201001\u201004, Department of Computer Science and Engineering, University of Washington, Seattle, WA, 1990."},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1137\/0217027"},{"key":"R36","unstructured":"V. Kumar, A. Grama, A. Gupta, and G. Kraypis,\n                      Introduction to Parallel Computing\n                      , Benjamin\/Cummings, 1994."},{"key":"R37","unstructured":"L. L. Larmore and W. Rytter,\n                      Efficient Sublinear Time Parallel Algorithms for the Recognition of Context\u2010Free Languages\n                      , SWAT 91, Springer Verlag, LNCS #577, 1991, pp. 121\u2013132."},{"key":"R38","unstructured":"P. Ramanan,\n                      A new lower bound technique and its application: Tight lower bounds for a polygon triangularization problem\n                      , Proc. 2nd Annual ACM\u2010SIAM Symposium on Discrete Algorithms, 1991, pp. 281\u2013290."},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539790190077"},{"key":"R40","unstructured":"P. Ramanan,\n                      An Efficient Parallel Algorithm for Finding an Optimal Order of Computing a Matrix Chain Product\n                      , Technical Report, WSUCS\u201092\u20102, Wichita State University, June, 1992."},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1137\/0225039"},{"key":"R42","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(88)90147-8"},{"key":"R43","doi-asserted-by":"publisher","DOI":"10.1137\/0212043"},{"key":"R44","doi-asserted-by":"publisher","DOI":"10.1137\/0603055"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539794270698","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:12:12Z","timestamp":1787335932000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539794270698"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":45,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539794270698"],"URL":"https:\/\/doi.org\/10.1137\/s0097539794270698","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}