research-article

Computation of Matrix Chain Products. Part I

Authors:

T. C. Hu,

M. T. ShingAuthors Info & Claims

SIAM Journal on Computing, Volume 11, Issue 2

Pages 362 - 373

https://doi.org/10.1137/0211028

Published: 01 May 1982 Publication History

Abstract

This paper considers the computation of matrix chain products of the form $M_1 \times M_2 \times \cdots \times M_{n - 1} $. If the matrices are of different dimensions, the order in which the product is computed affects the number of operations. An optimum order is an order which minimizes the total number of operations. We present some theorems about an optimum order of computing the matrices. Based on these theorems, an $O(n\log n)$ algorithm for finding an optimum order will be presented in Part II.

References

[1]

Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman, The design and analysis of computer algorithms, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975x+470

Google Scholar

[2]

A. K. Chandra, Computing matrix chain product in near optimum time, IBM Res. Rep., RC5626 (# 24393), IBM Thomas J. Watson Research Center, Yorktown Heights, NY, 1975

Google Scholar

[3]

Francis Y. Chin, An $O(n)$ algorithm for determining a near-optimal computation order of matrix chain products, Comm. ACM, 21 (1978), 544–549

Digital Library

Google Scholar

[4]

L. E. Deimel, Jr., T. A. Lamps, An invariance theorem concerning optimal computation of matrix chain products, Rep., TR79-14, North Carolina State Univ., Raleigh

Google Scholar

[5]

G. A. Dirac, On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg, 25 (1961), 71–76

Crossref

Google Scholar

[6]

M. Gardner, Catalan numbers, Scientific American, (1976), 120–124, June

Crossref

Google Scholar

[7]

S. S. Godbole, An efficient computation of matrix chain products, IEEE Trans. Comput., C-22 (1973), 864–866

Google Scholar

[8]

H. W. Gould, Bell and Catalan numbers, Combinatorial Research Institute, Morgantown, WV., 1977, June

Google Scholar

[9]

T. C. Hu, M. T. Shing, Computation of Matrix Chain Product, Amer. Math. Soc., 1 (1980), 336–, Abstract

Google Scholar

[10]

T. C. Hu, M. T. Shing, Some theorems about matrix multiplications, Proc. 21st Annual IEEE Symposium on the Foundations of Computer Science, 1980, 28–35, October

Google Scholar

[11]

T. C. Hu, M. T. Shing, Computation of matrix chain products, Proc. 1981 Army Numerical Analysis and Computations Conference, 1981, 615–628, August

Google Scholar

[12]

T. C. Hu, M. T. Shing, An $O(n)$ algorithm to find a near-optimum partition of a convex polygon, J. Algorithms, 2 (1981), 122–138

Crossref

Google Scholar

[13]

T. C. Hu, M.-T. Shing, Computation of matrix chain products. II, SIAM J. Comput., 13 (1984), 228–251

Digital Library

Google Scholar

Cited By

View all

Nissim RSchwartz OShabo R(2024)Challenges in Parallel Matrix Chain MultiplicationJob Scheduling Strategies for Parallel Processing10.1007/978-3-031-74430-3_7(120-140)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-74430-3_7
Psarras CBarthels HBientinesi P(2022)The Linear Algebra Mapping Problem. Current State of Linear Algebra Languages and LibrariesACM Transactions on Mathematical Software10.1145/354993548:3(1-30)Online publication date: 10-Sep-2022
https://dl.acm.org/doi/10.1145/3549935
Barthels HPsarras CBientinesi P(2021)LinneaACM Transactions on Mathematical Software10.1145/344663247:3(1-26)Online publication date: 26-Jun-2021
https://dl.acm.org/doi/10.1145/3446632
Show More Cited By

Index Terms

Computation of Matrix Chain Products. Part I

Index terms have been assigned to the content through auto-classification.

Recommendations

An O(n) algorithm for determining a near-optimal computation order of matrix chain products

This paper discusses the computation of matrix chain products of the form M₁ × M₂2 × ··· × M_n where M_i's are matrices. The order in which the matrices are computed affects the number of operations. A sufficient condition about the association of the ...
On Efficient Computation of Matrix Chain Products

It is pointed out that the number of scalar multiplications (additions) required to evaluate a matrix chain product depends on the sequence in which the associative law of matrix multiplication is applied. An algorithm is developed to find the optimum ...
Computation of matrix chain products

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SIAM Journal on Computing Volume 11, Issue 2

May 1982

208 pages

ISSN:0097-5397

DOI:10.1137/smjcat.1982.11.issue-2

Issue’s Table of Contents

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 May 1982

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 11 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Nissim RSchwartz OShabo R(2024)Challenges in Parallel Matrix Chain MultiplicationJob Scheduling Strategies for Parallel Processing10.1007/978-3-031-74430-3_7(120-140)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-74430-3_7
Psarras CBarthels HBientinesi P(2022)The Linear Algebra Mapping Problem. Current State of Linear Algebra Languages and LibrariesACM Transactions on Mathematical Software10.1145/354993548:3(1-30)Online publication date: 10-Sep-2022
https://dl.acm.org/doi/10.1145/3549935
Barthels HPsarras CBientinesi P(2021)LinneaACM Transactions on Mathematical Software10.1145/344663247:3(1-26)Online publication date: 26-Jun-2021
https://dl.acm.org/doi/10.1145/3446632
Barthels HCopik MBientinesi PKnoop JSchordan MJohnson TO'Boyle M(2018)The generalized matrix chain algorithmProceedings of the 2018 International Symposium on Code Generation and Optimization10.1145/3168804(138-148)Online publication date: 24-Feb-2018
https://dl.acm.org/doi/10.1145/3168804

Abstract

References

Cited By

Index Terms

Recommendations

An O(n) algorithm for determining a near-optimal computation order of matrix chain products

On Efficient Computation of Matrix Chain Products