File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: O(n) ALGORITHM FOR DETERMINING A NEAR-OPTIMAL COMPUTATION ORDER OF MATRIX CHAIN PRODUCTS.

TitleO(n) ALGORITHM FOR DETERMINING A NEAR-OPTIMAL COMPUTATION ORDER OF MATRIX CHAIN PRODUCTS.
Authors
Keywordsapproximate algorithm
heuristic algorithm
matrix chain product
matrix multiplication
Issue Date1978
PublisherAssociation for Computing Machinery, Inc. The Journal's web site is located at http://www.acm.org/cacm/
Citation
Communications Of The Acm, 1978, v. 21 n. 7, p. 544-549 How to Cite?
AbstractDiscussion of the computation of matrix chain products of the form M//1 multiplied by M//2 multiplied by . . . multiplied by 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 matrices in the optimal order is presented. An O(n) algorithm to find an order of computation which takes less than 25 percent longer than the optimal time T(opt) is also presented. In most cases, the algorithm yields the optimal order or an order which takes only a few percent longer than T(opt) (less than 1 percent on the average).
Persistent Identifierhttp://hdl.handle.net/10722/152202
ISSN
2023 Impact Factor: 11.1
2023 SCImago Journal Rankings: 2.957
ISI Accession Number ID

 

DC FieldValueLanguage
dc.contributor.authorChin, Francis Yen_US
dc.date.accessioned2012-06-26T06:36:30Z-
dc.date.available2012-06-26T06:36:30Z-
dc.date.issued1978en_US
dc.identifier.citationCommunications Of The Acm, 1978, v. 21 n. 7, p. 544-549en_US
dc.identifier.issn0001-0782en_US
dc.identifier.urihttp://hdl.handle.net/10722/152202-
dc.description.abstractDiscussion of the computation of matrix chain products of the form M//1 multiplied by M//2 multiplied by . . . multiplied by 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 matrices in the optimal order is presented. An O(n) algorithm to find an order of computation which takes less than 25 percent longer than the optimal time T(opt) is also presented. In most cases, the algorithm yields the optimal order or an order which takes only a few percent longer than T(opt) (less than 1 percent on the average).en_US
dc.languageengen_US
dc.publisherAssociation for Computing Machinery, Inc. The Journal's web site is located at http://www.acm.org/cacm/en_US
dc.relation.ispartofCommunications of the ACMen_US
dc.subjectapproximate algorithm-
dc.subjectheuristic algorithm-
dc.subjectmatrix chain product-
dc.subjectmatrix multiplication-
dc.titleO(n) ALGORITHM FOR DETERMINING A NEAR-OPTIMAL COMPUTATION ORDER OF MATRIX CHAIN PRODUCTS.en_US
dc.typeArticleen_US
dc.identifier.emailChin, Francis Y:chin@cs.hku.hken_US
dc.identifier.authorityChin, Francis Y=rp00105en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1145/359545.359556en_US
dc.identifier.scopuseid_2-s2.0-0017995317en_US
dc.identifier.volume21en_US
dc.identifier.issue7en_US
dc.identifier.spage544en_US
dc.identifier.epage549en_US
dc.identifier.isiWOS:A1978FG43300003-
dc.publisher.placeUnited Statesen_US
dc.identifier.scopusauthoridChin, Francis Y=7005101915en_US
dc.identifier.issnl0001-0782-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats