Paolo Bientinesi
Enrique S. Quintana-Ortí
Robert A. van de Geijn
Skip Abstract Section
Abstract
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.
- Alpatov, P., Baker, G., Edwards, C., Gunnels, J., Morrow, G., Overfelt, J., van de Geijn, R., and Wu, Y.-J. J. 1997. PLAPACK: Parallel linear algebra package---design overview. In Proceedings of SC97. Google Scholar
- 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.Google Scholar
- Bientinesi, P. and van de Geijn, R. A. 2002. Developing linear algebra algorithms: Class projects Spring 2002. Tech. Rep. CS-TR-02, Department of Computer Sciences, The University of Texas at Austin. June. http://www.cs.utexas.edu/users/flame/pubs/.Google Scholar
- Dijkstra, E. W. 1968. A constructive approach to the problem of program correctness. BIT 8, 174--186.Google Scholar
- Dijkstra, E. W. 1976. A Discipline of Programming. Prentice-Hall. Google Scholar
- Dongarra, J. J., Du Croz, J., Hammarling, S., and Duff, I. 1990. A set of level 3 basic linear algebra subprograms. ACM Trans. Math. Soft. 16, 1 (March), 1--17. Google Scholar
- Dongarra, J. J., Du Croz, J., Hammarling, S., and Hanson, R. J. 1988. An extended set of FORTRAN basic linear algebra subprograms. ACM Trans. Math. Soft. 14, 1 (March), 1--17. Google Scholar
- Ernst, M. D. 2000. Dynamically discovering likely program invariants. Ph.D. thesis, University of Washington Department of Computer Science and Engineering. Google Scholar
- 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. Google Scholar
- Floyd, R. W. 1967. Assigning meanings to programs. In Symposium on Applied Mathematics, J. T. Schwartz, Ed. Vol. 19. American Mathematical Society, 19--32.Google Scholar
- Gries, D. 1981. The Science of Programming. Springer-Verlag. Google Scholar
- Gries, D. and Schneider, F. B. 1992. A Logical Approach to Discrete Math. Texts and Monographs in Computer Science. Springer-Verlag. Google Scholar
- Gunnels, J. A. 2001. A systematic approach to the design and analysis of parallel dense linear algebra algorithms. Ph.D. thesis, Department of Computer Sciences, The University of Texas. Google Scholar
- Gunnels, J. A., Gustavson, F. G., Henry, G. M., and van de Geijn, R. A. 2001. FLAME: Formal linear algebra methods environment. ACM Trans. Math. Soft. 27, 4 (December), 422--455. Google Scholar
- 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. Google Scholar
- Gunnels, J. A. and van de Geijn, R. A. 2001a. Developing linear algebra algorithms: A collection of class projects. Tech. Rep. CS-TR-01-19, Department of Computer Sciences, The University of Texas at Austin. May. http://www.cs.utexas.edu/users/flame/. Google Scholar
- 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. Google Scholar
- Higham, N. J. 2002. Accuracy and Stability of Numerical Algorithms, Second ed. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA. Google Scholar
- Hoare, C. A. R. 1969. An axiomatic basis for computer programming. Comm. ACM 12, 12 (October), 576--580. Google Scholar
- Kaufman, M. and Moore, J. S. 1997. An industrial strength theorem prover for a logic based on common lisp. IEEE Trans. Soft. Eng. 23, 4 (April), 203--213. Google Scholar
- Kaufmann, M., Manolios, P., and Moore, J. S., Eds. 2000. Computer-Aided Reasoning: ACL2 Case Studies. Kluwer Academic Publishers. Google Scholar
- Lawson, C. L., Hanson, R. J., Kincaid, D. R., and Krogh, F. T. 1979. Basic linear algebra subprograms for Fortran usage. ACM Trans. Math. Soft. 5, 3 (Sept.), 308--323. Google Scholar
- Misra, J. 1976. Some aspects of the verification of loop computations. IEEE Trans. Soft. Eng. SE-4, 6 (Nov.).Google Scholar
- Moler, C., Little, J., and Bangert, S. 1987. Pro-Matlab, User's Guide. The Mathworks, Inc.Google Scholar
- Quintana, E. S., Quintana, G., Sun, X., and van de Geijn, R. 2001. A note on parallel matrix inversion. SIAM J. Sci. Comput. 22, 5, 1762--1771. Google Scholar
- Quintana-Ortí, E. S. and van de Geijn, R. A. 2003. Formal derivation of algorithms for the triangular Sylvester equation. ACM Trans. Math. Soft. 29, 2 (July), 218--243. Google Scholar
- van de Geijn, R. A. 1997. Using PLAPACK: Parallel Linear Algebra Package. The MIT Press. Google Scholar
- Whaley, R. C. and Dongarra, J. J. 1998. Automatically tuned linear algebra software. In Proceedings of SC'98. Google Scholar
- Wolfram, S. 1996. The Mathematica Book: 3rd Edition. Cambridge University Press. Google Scholar
Index Terms
- The science of deriving dense linear algebra algorithms
Recommendations
Representing linear algebra algorithms in code: the FLAME application program interfaces
In this article, we present a number of Application Program Interfaces (APIs) for coding linear algebra algorithms. On the surface, these APIs for the MATLAB M-script and C programming languages appear to be simple, almost trivial, extensions of those ...
Deriving dense linear algebra libraries
AbstractStarting in the late 1960s computer scientists including Dijkstra and Hoare advocated goal-oriented programming and the formal derivation of algorithms. The chief impediment to realizing this for loop-based programs was that a priori determination ...
Typing linear algebra: A biproduct-oriented approach
Interested in formalizing the generation of fast running code for linear algebra applications, the authors show how an index-free, calculational approach to matrix algebra can be developed by regarding matrices as morphisms of a category with ...
Comments