{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T09:04:03Z","timestamp":1774602243038,"version":"3.50.1"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2005,3,1]],"date-time":"2005-03-01T00:00:00Z","timestamp":1109635200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2005,3]]},"abstract":"<jats:p>In this article we present a systematic approach to the derivation of families of high-performance algorithms for a large set of frequently encountered dense linear algebra operations. As part of the derivation a constructive proof of the correctness of the algorithm is generated. The article is structured so that it can be used as a tutorial for novices. However, the method has been shown to yield new high-performance algorithms for well-studied linear algebra operations and should also be of interest to those who wish to produce best-in-class high-performance codes.<\/jats:p>","DOI":"10.1145\/1055531.1055532","type":"journal-article","created":{"date-parts":[[2005,8,3]],"date-time":"2005-08-03T08:30:55Z","timestamp":1123057855000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":95,"title":["The science of deriving dense linear algebra algorithms"],"prefix":"10.1145","volume":"31","author":[{"given":"Paolo","family":"Bientinesi","sequence":"first","affiliation":[{"name":"The University of Texas at Austin, Austin, TX"}]},{"given":"John A.","family":"Gunnels","sequence":"additional","affiliation":[{"name":"IBM T.J. Watson Research Center, Yorktown Heights, NY"}]},{"given":"Margaret E.","family":"Myers","sequence":"additional","affiliation":[{"name":"The University of Texas at Austin, Austin, TX"}]},{"given":"Enrique S.","family":"Quintana-Ort\u00ed","sequence":"additional","affiliation":[{"name":"Universidad Jaume I, Spain"}]},{"given":"Robert A. van de","family":"Geijn","sequence":"additional","affiliation":[{"name":"The University of Texas at Austin, Austin, TX"}]}],"member":"320","published-online":{"date-parts":[[2005,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/509593.509622"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of Performance Optimization for High-Level Languages and Libraries (POHLL-02)","author":"Bientinesi P.","unstructured":"Bientinesi , P. , Gunnels , J. A. , Gustavson , F. G. , Henry , G. M. , Myers , M. E. , Quintana-Orti , E. S. , and van de Geijn, R. A. 2002. The science of programming high-performance linear algebra libraries . In Proceedings of Performance Optimization for High-Level Languages and Libraries (POHLL-02) . To appear. Bientinesi, P., Gunnels, J. A., Gustavson, F. G., Henry, G. M., Myers, M. E., Quintana-Orti, E. S., and van de Geijn, R. A. 2002. The science of programming high-performance linear algebra libraries. In Proceedings of Performance Optimization for High-Level Languages and Libraries (POHLL-02). To appear."},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1007\/BF01933419","article-title":"A constructive approach to the problem of program correctness","volume":"8","author":"Dijkstra E. W.","year":"1968","unstructured":"Dijkstra , E. W. 1968 . A constructive approach to the problem of program correctness . BIT 8 , 174 -- 186 . Dijkstra, E. W. 1968. A constructive approach to the problem of program correctness. BIT 8, 174--186.","journal-title":"BIT"},{"key":"e_1_2_1_5_1","volume-title":"A Discipline of Programming","author":"Dijkstra E. W.","unstructured":"Dijkstra , E. W. 1976. A Discipline of Programming . Prentice-Hall . Dijkstra, E. W. 1976. A Discipline of Programming. Prentice-Hall."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/77626.79170"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/42288.42291"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 22nd International Conference on Software Engineering (ICSE","author":"Ernst M. D.","year":"2000","unstructured":"Ernst , M. D. , Czeisler , A. , Griswold , W. G. , and Notkin , D . 2000. Quickly detecting relevant program invariants . In Proceedings of the 22nd International Conference on Software Engineering (ICSE 2000 ). 449--458. 10.1145\/337180.337240 Ernst, M. D., Czeisler, A., Griswold, W. G., and Notkin, D. 2000. Quickly detecting relevant program invariants. In Proceedings of the 22nd International Conference on Software Engineering (ICSE 2000). 449--458. 10.1145\/337180.337240"},{"key":"e_1_2_1_10_1","volume-title":"Symposium on Applied Mathematics, J. T. Schwartz, Ed.","volume":"19","author":"Floyd R. W.","year":"1967","unstructured":"Floyd , R. W. 1967 . Assigning meanings to programs . In Symposium on Applied Mathematics, J. T. Schwartz, Ed. Vol. 19 . American Mathematical Society, 19--32. Floyd, R. W. 1967. Assigning meanings to programs. In Symposium on Applied Mathematics, J. T. Schwartz, Ed. Vol. 19. American Mathematical Society, 19--32."},{"key":"e_1_2_1_11_1","volume-title":"The Science of Programming","author":"Gries D.","unstructured":"Gries , D. 1981. The Science of Programming . Springer-Verlag . Gries, D. 1981. The Science of Programming. Springer-Verlag."},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Gries D. and Schneider F. B. 1992. A Logical Approach to Discrete Math. Texts and Monographs in Computer Science. Springer-Verlag.   Gries D. and Schneider F. B. 1992. A Logical Approach to Discrete Math. Texts and Monographs in Computer Science. Springer-Verlag.","DOI":"10.1007\/978-1-4757-3837-7"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/504210.504213"},{"key":"e_1_2_1_15_1","volume-title":"Computational Science---ICCS","author":"Gunnels J. A.","year":"2001","unstructured":"Gunnels , J. A. , Henry , G. M. , and van de Geijn , R. A. 2001. A family of high-performance matrix multiplication algorithms . In Computational Science---ICCS 2001 , Part I, V. N. Alexandrov, J. J. Dongarra, B. A. Juliano, R. S. Renner, and C. K. Tan, Eds. Lecture Notes in Computer Science 2073. Springer-Verlag , 51--60. Gunnels, J. A., Henry, G. M., and van de Geijn, R. A. 2001. A family of high-performance matrix multiplication algorithms. In Computational Science---ICCS 2001, Part I, V. N. Alexandrov, J. J. Dongarra, B. A. Juliano, R. S. Renner, and C. K. Tan, Eds. Lecture Notes in Computer Science 2073. Springer-Verlag, 51--60."},{"key":"e_1_2_1_17_1","volume-title":"The Architecture of Scientific Software","author":"Gunnels J. A.","unstructured":"Gunnels , J. A. and van de Geijn , R. A. 2001b. Formal methods for high-performance linear algebra libraries . In The Architecture of Scientific Software , R. F. Boisvert and P. T. P. Tang, Eds. Kluwer Academic Press , 193--210. Gunnels, J. A. and van de Geijn, R. A. 2001b. Formal methods for high-performance linear algebra libraries. In The Architecture of Scientific Software, R. F. Boisvert and P. T. P. Tang, Eds. Kluwer Academic Press, 193--210."},{"key":"e_1_2_1_18_1","volume-title":"Accuracy and Stability of Numerical Algorithms","author":"Higham N. J.","unstructured":"Higham , N. J. 2002. Accuracy and Stability of Numerical Algorithms , Second ed. Society for Industrial and Applied Mathematics , Philadelphia, PA, USA . Higham, N. J. 2002. Accuracy and Stability of Numerical Algorithms, Second ed. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/363235.363259"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.588534"},{"key":"e_1_2_1_21_1","volume-title":"Eds","author":"Kaufmann M.","year":"2000","unstructured":"Kaufmann , M. , Manolios , P. , and Moore , J. S. , Eds . 2000 . Computer-Aided Reasoning: ACL2 Case Studies . Kluwer Academic Publishers . Kaufmann, M., Manolios, P., and Moore, J. S., Eds. 2000. Computer-Aided Reasoning: ACL2 Case Studies. Kluwer Academic Publishers."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/355841.355847"},{"key":"e_1_2_1_23_1","article-title":"Some aspects of the verification of loop computations","volume":"6","author":"Misra J.","year":"1976","unstructured":"Misra , J. 1976 . Some aspects of the verification of loop computations . IEEE Trans. Soft. Eng. SE-4 , 6 ( Nov. ). Misra, J. 1976. Some aspects of the verification of loop computations. IEEE Trans. Soft. Eng. SE-4, 6 (Nov.).","journal-title":"IEEE Trans. Soft. Eng. SE-4"},{"key":"e_1_2_1_24_1","unstructured":"Moler C. Little J. and Bangert S. 1987. Pro-Matlab User's Guide. The Mathworks Inc.  Moler C. Little J. and Bangert S. 1987. Pro-Matlab User's Guide. The Mathworks Inc."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827598345679"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/779359.779365"},{"key":"e_1_2_1_27_1","volume-title":"Using PLAPACK: Parallel Linear Algebra Package","author":"van de Geijn R. A.","unstructured":"van de Geijn , R. A. 1997. Using PLAPACK: Parallel Linear Algebra Package . The MIT Press . van de Geijn, R. A. 1997. Using PLAPACK: Parallel Linear Algebra Package. The MIT Press."},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of SC'98","author":"Whaley R. C.","unstructured":"Whaley , R. C. and Dongarra , J. J . 1998. Automatically tuned linear algebra software . In Proceedings of SC'98 . Whaley, R. C. and Dongarra, J. J. 1998. Automatically tuned linear algebra software. In Proceedings of SC'98."},{"key":"e_1_2_1_29_1","volume-title":"The Mathematica Book","author":"Wolfram S.","unstructured":"Wolfram , S. 1996. The Mathematica Book : 3 rd Edition. Cambridge University Press . Wolfram, S. 1996. The Mathematica Book: 3rd Edition. Cambridge University Press.","edition":"3"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1055531.1055532","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1055531.1055532","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:31:27Z","timestamp":1750264287000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1055531.1055532"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,3]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2005,3]]}},"alternative-id":["10.1145\/1055531.1055532"],"URL":"https:\/\/doi.org\/10.1145\/1055531.1055532","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"value":"0098-3500","type":"print"},{"value":"1557-7295","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,3]]},"assertion":[{"value":"2005-03-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}