FORTRAN codes for estimating the one-norm of a real or complex matrix, with applications to condition estimation

ABSTRACT

FORTRAN 77 codes SONEST and CONEST are presented for estimating the 1-norm ( or the infinity-norm) of a real or complex matrix, respectively. The codes are of wide applicability in condition estimation since explicit access to the matrix, A, is not required; instead, matrix-vector products Ax and ATx are computed by the calling program via a reverse communication interface. The algorithms are based on a convex optimization method for estimating the 1-norm of a real matrix devised by Hager. We derive new results concerning the behavior of Hager's method, extend it to complex matrices, and make several algorithmic modifications in order to improve the reliability and efficiency.

REFERENCES

• 1: BYERS, R. A LINPACK-style condition estimator for the equation AX - XBr = C. IEEE Trans. Automat. Control AC-29 (1984), 926-928.
• 2: Eleanor Chu , Alan George, A note on estimating the error in Gaussian elimination without pivoting, ACM SIGNUM Newsletter, v.20 n.2, p.2-7, April 1985 [doi>10.1145/1057941.1057942]
• 3: CLINE, A. K., AND REW, R.K. A set of counter-examples to three condition number estimators. SIAM J. Sci. Stat. Comput. 4, 4 (1983), 602-611.
• 4: Jack J Dongarra , Eric Grosse, Distribution of mathematical software via electronic mail, Communications of the ACM, v.30 n.5, p.403-407, May 1987 [doi>10.1145/22899.22904]
• 5: J J Dongarra , D C Sorensen, Linear algebra on high-performance computers, Applied Mathematics and Computation, v.20 n.1-2, p.57-88, Sept. 1986 [doi>10.1016/0096-3003(86)90126-8]
• 6: Iain S Duff , Albert M Erisman , John K Reid, Direct methods for sparse matrices, Oxford University Press, Inc., New York, NY, 1986
• 7: EDLEFSEN, L. E., AND JONES, S.D. GAUSS programming language manual. Aptech Systems, Kent, Wash., 1986.
• 8: R. Fletcher, Practical methods of optimization; (2nd ed.), Wiley-Interscience, New York, NY, 1987
• 9: GOLUB, G. H., NASH, S., AND VAN LOAN, C.F. A Hessenberg-Schur method for the problem AX + XB - C. IEEE Trans. Automat. Control AC-24 (1979), 909-913.
• 10: GRIMES, R. G., AND LEWIS, J.G. Condition number estimation for sparse matrices. SIAM J. Sci. Stat. Comput. 2, 4 (1981), 384-388.
• 11: HAGER, W.W. Condition estimates. SIAM J. Sci. Star. Comput. 5, 2 (1984), 311-316.
• 12: HAGER, W.W. Applied Numerical Linear Algebra. Prentice-Hall, Englewood Cliffs, N.J., 1988.
• 13: HAMMARLING, S.J. Numerical solution of the stable, non-negative definite Lyapunov equation. IMA J. Numer. Anal. 2 (1982), 303-323.
• 14: Nicholas J. Highham, A survey of condition number estimation for triangular matrices, SIAM Review, v.29 n.4, p.575-596, December 1, 1987 [doi>10.1137/1029112]
• 15: HOFFMAN, W., AND LIOEN, W.M. NUMVEC Fortran library manual, Chapter: Simultaneous equations. Rep. NM-R8614, Centre for Mathematics and Computer Science, Amsterdam, 1986.
• 16: HOSKINS, W. D., MEEK, D. S., AND WALTON, D.J. The numerical solution of the matrix equation XA + A Y = F. BIT 17 (1977), 184-190.
• 17: K/~GSTROM, B., AND WESTIN, L. Generalized Schur methods with condition estimators for solving the generalized Sylvester equation. Rep. UMINF-130.86, Institute of Information Processing, Univ. of Umea, Umea, Sweden, 1986; revised July 1987.
• 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: MOLER, C. B., LITTLE, J. N., AND BANGERT, S. PC-Matlab User's Guide. The MathWorks, Sherborn, Mass., 1987.
• 20: O'LEAR~, D.P. Estimating matrix condition numbers. SIAM J. Sci. Stat. Cornput. 1, 2 (1980), 205-209.
• 21: M. L. Pei, A test matrix for inversion procedures, Communications of the ACM, v.5 n.10, p.508, Oct. 1962 [doi>10.1145/368959.368975]
• 22: Zahari Zlatev , Jerzy Wasniewski , Kjeld Schaumburg, Condition number estimators in a sparse matrix software, SIAM Journal on Scientific and Statistical Computing, v.7 n.4, p.1175-1189, Oct. 1986 [doi>10.1137/0907080]

INDEX TERMS

Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra

General Terms:
Algorithms

Keywords:
FORTRAN, LINPACK, condition estimation, condition number, convex optimization, infinity-norm, one-norm, reverse communication