File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1145/359545.359556
- Scopus: eid_2-s2.0-0017995317
- WOS: WOS:A1978FG43300003
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: O(n) ALGORITHM FOR DETERMINING A NEAR-OPTIMAL COMPUTATION ORDER OF MATRIX CHAIN PRODUCTS.
| Title | O(n) ALGORITHM FOR DETERMINING A NEAR-OPTIMAL COMPUTATION ORDER OF MATRIX CHAIN PRODUCTS. |
|---|---|
| Authors | |
| Keywords | approximate algorithm heuristic algorithm matrix chain product matrix multiplication |
| Issue Date | 1978 |
| Publisher | Association 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? |
| Abstract | Discussion 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 Identifier | http://hdl.handle.net/10722/152202 |
| ISSN | 2023 Impact Factor: 11.1 2023 SCImago Journal Rankings: 2.957 |
| ISI Accession Number ID |
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Chin, Francis Y | en_US |
| dc.date.accessioned | 2012-06-26T06:36:30Z | - |
| dc.date.available | 2012-06-26T06:36:30Z | - |
| dc.date.issued | 1978 | en_US |
| dc.identifier.citation | Communications Of The Acm, 1978, v. 21 n. 7, p. 544-549 | en_US |
| dc.identifier.issn | 0001-0782 | en_US |
| dc.identifier.uri | http://hdl.handle.net/10722/152202 | - |
| dc.description.abstract | Discussion 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.language | eng | en_US |
| dc.publisher | Association for Computing Machinery, Inc. The Journal's web site is located at http://www.acm.org/cacm/ | en_US |
| dc.relation.ispartof | Communications of the ACM | en_US |
| dc.subject | approximate algorithm | - |
| dc.subject | heuristic algorithm | - |
| dc.subject | matrix chain product | - |
| dc.subject | matrix multiplication | - |
| dc.title | O(n) ALGORITHM FOR DETERMINING A NEAR-OPTIMAL COMPUTATION ORDER OF MATRIX CHAIN PRODUCTS. | en_US |
| dc.type | Article | en_US |
| dc.identifier.email | Chin, Francis Y:chin@cs.hku.hk | en_US |
| dc.identifier.authority | Chin, Francis Y=rp00105 | en_US |
| dc.description.nature | link_to_subscribed_fulltext | en_US |
| dc.identifier.doi | 10.1145/359545.359556 | en_US |
| dc.identifier.scopus | eid_2-s2.0-0017995317 | en_US |
| dc.identifier.volume | 21 | en_US |
| dc.identifier.issue | 7 | en_US |
| dc.identifier.spage | 544 | en_US |
| dc.identifier.epage | 549 | en_US |
| dc.identifier.isi | WOS:A1978FG43300003 | - |
| dc.publisher.place | United States | en_US |
| dc.identifier.scopusauthorid | Chin, Francis Y=7005101915 | en_US |
| dc.identifier.issnl | 0001-0782 | - |