Formal derivation of algorithms: The triangular sylvester equation

ABSTRACT

In this paper we apply a formal approach for the derivation of dense linear algebra algorithms to the triangular Sylvester equation. The result is a large family of provably correct algorithms. By using a coding style that reflects the algorithms as they are naturally presented, the correctness of the algorithms carries through to the correctness of the implementations. Analytically motivated heuristics are used to subsequently choose members from the family that can be expected to yield high performance. Finally, we report performance on the Intel (R) Pentium (R) III processor that is competitive with that of recursive algorithms reported previously in the literature for this operation.

REFERENCES

• 1: Aliev, F. and Larin, V. 1998. Optimization of Linear Control Systems: Analytical Methods and Computational Algorithms. Stability and Control: Theory, Methods and Applications, vol. 8. Gordon and Breach, New York, NY.
• 2: E. Anderson , Z. Bai , C. Bischof , J. Demmel , J. Dongarra , J. Du Croz , A. Greenbaum , S. Hammarling , A. McKenney , S. Ostrouchov , D. Sorensen, LAPACK's user's guide, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 3: R. H. Bartels , G. W. Stewart, Solution of the matrix equation AX + XB = C [F4], Communications of the ACM, v.15 n.9, p.820-826, Sept. 1972 [doi>10.1145/361573.361582]
• 4: Bientinesi, P., Gunnels, J. A., Myers, M. E., Quintana-Orí, E. S., and van de Geijn, R. A. 2002. The science of deriving dense linear algebra algorithms. Tech. Rep. CS-TR-02-53, Department of Computer Sciences, The University of Texas at Austin, Austin, TX. Available online at http://www.cs.utexas.edu/users/flame/.
• 5: Jeff Bilmes , Krste Asanovic , Chee-Whye Chin , Jim Demmel, Optimizing matrix multiply using PHiPAC: a portable, high-performance, ANSI C coding methodology, Proceedings of the 11th international conference on Supercomputing, p.340-347, July 07-11, 1997, Vienna, Austria [doi>10.1145/263580.263662]
• 6: D. Calvetti , L. Reichel, Application of ADI Iterative Methods to the Restoration of Noisy Images, SIAM Journal on Matrix Analysis and Applications, v.17 n.1, p.165-186, Jan. 1996 [doi>10.1137/S0895479894273687]
• 7: J. J. Dongarra , Jeremy Du Croz , Sven Hammarling , I. S. Duff, A set of level 3 basic linear algebra subprograms, ACM Transactions on Mathematical Software (TOMS), v.16 n.1, p.1-17, March 1990 [doi>10.1145/77626.79170]
• 8: Jack J. Dongarra , Jeremy Du Croz , Sven Hammarling , Richard J. Hanson, An extended set of FORTRAN basic linear algebra subprograms, ACM Transactions on Mathematical Software (TOMS), v.14 n.1, p.1-17, March 1988 [doi>10.1145/42288.42291]
• 9: Judith D. Gardiner , Alan J. Laub , James J. Amato , Cleve B. Moler, Solution of the Sylvester matrix equation AXBT + CXDT = E, ACM Transactions on Mathematical Software (TOMS), v.18 n.2, p.223-231, June 1992 [doi>10.1145/146847.146929]
• 10: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 11: Golub, G. H., Nash, S., and Van Loan, C. F. 1979. A Hessenberg--Schur method for the problem AX + XB = C. IEEE Trans. Automat. Control AC-24, 6, 909--913.
• 12: John A. Gunnels , Fred G. Gustavson , Greg M. Henry , Robert A. van de Geijn, FLAME: Formal Linear Algebra Methods Environment, ACM Transactions on Mathematical Software (TOMS), v.27 n.4, p.422-455, December 2001 [doi>10.1145/504210.504213]
• 13: John A. Gunnels , Greg M. Henry , Robert A. van de Geijn, A Family of High-Performance Matrix Multiplication Algorithms, Proceedings of the International Conference on Computational Sciences-Part I, p.51-60, May 28-30, 2001
• 14: Hammarling, S. J. 1982. Numerical solution of the stable, non-negative definite Lyapunov equation. IMA J. Numer. Anal. 2, 303--323.
• 15: Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2002
• 16: Jonsson, I. and Kågström, B. 2001. Recursive blocked algorithms for solving triangular matrix equations---part I: one-sided and coupled Sylvester equations. Department of Computing Science and HPC2N Report UMINF-01.05. Umeå University, Umeå, Sweden.
• 17: Bo Kågström , Peter Poromaa, Distributed and shared memory block algorithms for the triangular Sylvester equation with sep-1 estimators, SIAM Journal on Matrix Analysis and Applications, v.13 n.1, p.90-101, Jan. 1992 [doi>10.1137/0613009]
• 18: C. L. Lawson , R. J. Hanson , D. R. Kincaid , F. T. Krogh, Basic Linear Algebra Subprograms for Fortran Usage, ACM Transactions on Mathematical Software (TOMS), v.5 n.3, p.308-323, Sept. 1979 [doi>10.1145/355841.355847]
• 19: Sima, V. 1996. Algorithms for Linear-Quadratic Optimization. Pure and Applied Mathematics, vol. 200. Marcel Dekker. New York, NY.
• 20: The MathWorks, Inc. 1993. The MATLAB Control Toolbox, Version 3.0b. The MathWorks, Inc., Natick, MA.
• 21: R. Clint Whaley , Jack J. Dongarra, Automatically tuned linear algebra software, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-27, November 07-13, 1998, San Jose, CA

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
        D.2.11 Software Architectures
            Subjects: Domain-specific architectures
      D.2.2 Design Tools and Techniques
          Subjects: Software libraries

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: User interfaces; Efficiency

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
Formal derivation, Sylvester equations, control theory, libraries, linear algebra