Skip to main content
SpringerLink
Log in

Report on test matrices for generalized inverses

Bericht über Testmatrizen für verallgemeinerte Inversen

  • Contributed Papers
  • Published:
Computing Aims and scope Submit manuscript

Abstract

This paper is a comprehensive report on test matrices for the generalized inversion of matrices. Two principles are described how to construct singular square or arbitrary rectangular test matrices and their Moore-Penrose inverses. By prescribing the singular values of the matrices or by suitably choosing the free parameters test matrices with condition numbers of any size can be obtained. We also deal with test matrices which are equal to their Moore-Penrose inverse. In addition to many advices how to construct test matrices the paper presents many test matrices explicitly, in particular singular square matrices of ordern, sets of 7×6 and 7×5 matrices of different rank, a set of 5×5 matrices which are equal to their Moore-Penrose inverse and some special test matrices known from literature. For the set of 7×6 parameter matrices also the singular values corresponding to six values of the parameter are listed. For three simple parameter matrices of order 5×4 and 6×5 even test results obtained by eight different algorithms are quoted.

As “by-products” the paper contains inequalities between condition numbers of different norms, representations for unitary, orthogonal, column-orthogonal and row-orthogonal matrices, a generalization of Hadamard matrices and representations of matrices which are equal to their Moore-Penrose inverse (or their inverse). All test matrices given in this paper may also be used for testing algorithms solving linear least squares problems.

Zusammenfassung

Diese Arbeit stellt einen umfassenden Bericht über Testmatrizen für die verallgemeinerte Matrizeninversion dar. Es werden zwei Prinzipien beschrieben, wie man singuläre quadratische oder beliebige rechteckige Testmatrizen und ihre Moore-Penrose-Inversen konstruieren kann. Durch die Vorgabe der singulären Werte der Matrizen oder durch geeignete Wahl der freien Parameter können die Testmatrizen beliebig große Konditionszahlen annehmen. Es wird auch auf Testmatrizen eingegangen, die gleich ihrer Moore-Penrose-Inversen sind. Neben vielen Hinweisen, wie man selbst Testmatrizen konstruieren kann, werden in der Arbeit zahlreiche Testmatrizen explizit angegeben, insbesondere singuläre quadratische Matrizenn-ter Ordnung, Serien von (7×6)- und (7×5)-Matrizen verschiedenen Ranges, eine Serie von (5×5)-Matrizen, die gleich ihrer Moore-Penrose-Inversen sind und einige spezielle Testmatrizen aus der Literatur. Für die Serie der (7×6)-Parametermatrizen sind die singulären Werte für sechs Werte des Parameters mit angegeben. Für drei einfache Parametermatrizen vom Format 5×4 und 6×5 sind auch die mit acht verschiedenen Algorithmen erzielten Testergebnisse aufgeführt.

Als „Nebenergebnisse” enthält die Arbeit Ungleichungen zwischen Konditionszahlen unterschiedlicher Normen, Darstellungen für unitäre, orthogonale, spaltenorthogonale und zeilenorthogonale Matrizen, eine Verallgemeinerung der Hadamard-Matrizen und Darstellungen von Matrizen, die gleich ihrer Moore-Penrose-Inversen (oder ihrer Inversen) sind. Die in der Arbeit aufgeführten Testmatrizen können auch zum Testen von Algorithmen zur Lösung von linearen Kleinste-Quadrate-Problemen verwendet werden.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Abdelmalek, N. N.: Round off error analysis for Gram-Schmidt method and solution of linear least squares problems. BIT11, 345–367 (1971).

    Google Scholar 

  2. Abdelmalek, N. N.: On the solution of the linear least squares problems and pseudo-inverses. Computing13, 215–228 (1974).

    Google Scholar 

  3. Bellman, R.: Introduction to matrix analysis. 328 pp. New York-Toronto-London: McGraw-Hill 1960.

    Google Scholar 

  4. Ben-Israel, A., Greville, T. N. E.: Generalized inverses: Theory and applications. 395 pp. New York: Wiley-Interscience 1974.

    Google Scholar 

  5. Berman, A.: Nonnegative matrices which are equal to their generalized inverse. Linear Algebra Appl.9, 261–265 (1974).

    Google Scholar 

  6. Björck, Å.: Solving linear least squares problems by Gram-Schmidt orthogonalization. BIT7, 1–21 (1967).

    Google Scholar 

  7. Björck, Å., Golub, G.: Iterative refinement of linear least squares solutions by Householder transformation. BIT7, 322–337 (1967).

    Google Scholar 

  8. Campbell, S. L., Meyer, C. D. Jr.: Generalized inverses of linear transformations. 272 pp. London-San Francisco-Melbourne: Pitman 1979.

    Google Scholar 

  9. Deuflhard, P., Sautter, W.: On rank-deficient pseudoinverses. Linear Algebra Appl.29, 91–111 (1980).

    Google Scholar 

  10. Drygalla, V.: Zur Darstellung und Berechnung von verallgemeinerten inversen Matrizen. Doctoral Dissertation, Martin-Luther-Univ. Halle-Wittenberg, Fak. für Naturwiss. d. Wiss. Rates, Halle 1980, 122 pp.

    Google Scholar 

  11. Faddeev, D. K., Faddeeva, V. N.: Computational methods of linear algebra. 621 pp. San Francisco: Freeman & Co. 1963.

    Google Scholar 

  12. Forsythe, G. E., Moler, C. B.: Computer solution of linear algebraic systems. 148 pp. Englewood Cliffs, N.J.: Prentice-Hall 1967.

    Google Scholar 

  13. Givens, W.: Numerical computation of the characteristic values of a real symmetric matrix. Report ORNL 1574. Oak Ridge National Laboratory, Oak Ridge, Tennessee, 1954, 107 pp.

    Google Scholar 

  14. Goldstine, H. H., von Neumann, J.: Numerical inverting of matrices of high order. II. Proc. Amer. Math. Soc.2, 188–202 (1951).

    Google Scholar 

  15. Golub, G., Kahan, W.: Calculating the singular values and pseudo-inverse of a matrix. SIAM J. Numer. Anal.2, 205–224 (1965).

    Google Scholar 

  16. Golub, G., Klema, V., Stewart, G. W.: Rank degeneracy and least squares problems. Stan-CS-76-559, Computer Science Department, Stanford Univ., Stanford, Calif., 1976; also as Technical Report TR-456, Computer Science Technical Report Series, Univ. of Maryland, College Park, Maryland, June 1976, 38 pp.

    Google Scholar 

  17. Golub, G. H., Reinsch, C.: Singular value decomposition and least squares solutions. Numer. Math.14, 403–420 (1970). Also in [75]. 134–151.

    Google Scholar 

  18. Gregory, R. T., Karney, D. L.: A collection of matrices for testing computational algorithms. 154 pp. New York-London-Sydney-Toronto: Wiley & Sons 1969.

    Google Scholar 

  19. Gröbner, W.: Matrizenrechnung. 279 pp. Mannheim-Wien-Zürich: Bibliographisches Institut 1966.

    Google Scholar 

  20. Householder, A. S.: The theory of matrices in numerical analysis. 257 pp. New York-Toronto-London: Blaisdell 1964.

    Google Scholar 

  21. Kymn, K. O., Norsworthy, J. R., Okamoto, T.: Alternative computing formulas for the generalized inverse and the evaluation of their performances. Econom. Lett.2, 37–43 (1979).

    Google Scholar 

  22. Kymn, K. O., Norsworthy, J. R., Okamoto, T.: The computation of the generalized inverse. Kyungpook Math. J.20, 199–206 (1980).

    Google Scholar 

  23. Lawson, C. L., Hanson, R. J.: Solving least squares problems. 340 pp. Englewood Cliffs, N.J.: Prentice-Hall 1974.

    Google Scholar 

  24. Longley, J. W.: An appraisal of least squares programs for the electronic computer from the point of view of the user. J. Amer. Statist. Assoc.62, 819–841 (1967).

    Google Scholar 

  25. Mirsky, L.: An introduction to linear algebra. 433 pp. London: Oxford Univ. Press 1955.

    Google Scholar 

  26. Moore, E. H.: On the reciprocal of the general algebraic matrix (Abstract). Bull. Amer. Math. Soc.26, 394–395 (1920).

    Google Scholar 

  27. Moore, E. H.: General analysis. Part I. Memoirs Amer. Philos. Soc., 1935, 231 pp., esp. 197–209.

  28. Von Neumann, J., Goldstine, H. H.: Numerical inverting of matrices of high order. Bull. Amer. Math. Soc.53, 1021–1099 (1947).

    Google Scholar 

  29. Newman, M., Todd, J.: The evaluation of matrix inversion programs. J. Soc. Indust. Appl. Math.6, 466–476 (1958).

    Google Scholar 

  30. Noble, B.: A method for computing the generalized inverse of a matrix. SIAM J. Numer. Anal.3, 582–584 (1966).

    Google Scholar 

  31. Noble, B.: Methods for computing the Moore-Penrose generalized inverse, and related matters. In: Generalized inverses and applications (Nashed, M. Z., ed.), pp. 245–301. New York-San Francisco-London: Academic Press 1976.

    Google Scholar 

  32. Paige, C. C., Saunders, M. A.: A bidiagonalization algorithm for sparse linear equations and least-squares problems. Technical Report SOL 78-19, Systems Optimization Laboratory, Department of Operations Research, Stanford University, Stanford, California, Oct. 1978, 89 pp.

    Google Scholar 

  33. Paige, C. C., Saunders, M. A.: LSQR: An algorithm for sparse linear equations and sparse least squares. ACM Trans. Math. Software8, 43–71 (1982).

    Google Scholar 

  34. Penrose, R.: A generalized inverse for matrices. Proc. Cambridge Philos. Soc.51, 406–413 (1955).

    Google Scholar 

  35. Penrose, R.: On best approximate solutions of linear matrix equations. Proc. Cambridge Philos. Soc.52, 17–19 (1956).

    Google Scholar 

  36. Pereyra, V., Rosen, J. B.: Computation of the pseudoinverse of a matrix of unknown rank. Tech. Rep. CS 13, Computer Science Div., Stanford University, Stanford, California, 1964, 28 pp.

    Google Scholar 

  37. Rao, T. M., Subramanian, K., Krishnamurthy, E. V.: Residue arithmetic algorithms for exact computation ofg-inverses of matrices. SIAM J. Numer. Anal.13, 155–171 (1976).

    Google Scholar 

  38. Rice, J. R.: SQUARS: An algorithm for least-squares approximation. In: Mathematical Software (Rice, J. R., ed.), pp. 451–476. New York-London: Academic Press 1971.

    Google Scholar 

  39. Rutishauser, H.: Once again: the least square problem. Linear Algebra Appl.1, 479–488 (1968).

    Google Scholar 

  40. Sautter, W.: Fehlerfortpflanzung und Rundungsfehler bei der verallgemeinerten Inversion von Matrizen. Doctoral Dissertation, TU München, München 1971, 85 pp.

    Google Scholar 

  41. Sautter, W.: Fehleranalyse für die Gauß-Elimination zur Berechnung der Lösung minimaler Länge. Numer. Math.30, 165–184 (1978).

    Google Scholar 

  42. Shinozaki, N., Sibuya, M., Tanabe, K.: Numerical algorithms for the Moore-Penrose inverse of a matrix: Direct methods. Ann. Inst. Statist. Math., Tokyo,24, 193–203 (1972).

    Google Scholar 

  43. Singh, I., Poole, G., Boullion, T.: A class of Hessenberg matrices with known pseudoinverse and Drazin inverse. Math. Comput.29, No. 130, 615–619 (1975).

    Google Scholar 

  44. Van der Sluis, A.: Stability of the solutions of linear least squares problems. Numer. Math.23, 241–254 (1975).

    Google Scholar 

  45. Smirnov, G. P.: Orthogonal integer matrices and methods for constructing them (Russian). Uchenye zapiski Bashgosuniversiteta, Ufa, Vyp.20, Ser. Mat. Nauk3, 316–321 (1968).

    Google Scholar 

  46. Söderström, T., Stewart, G. W.: On the numerical properties of an iterative method for computing the Moore-Penrose generalized inverse. SIAM J. Numer. Anal.11, 61–74 (1974).

    Google Scholar 

  47. Springer, J.: Berechnung der Moore-Penrose-Inversen einer Matrix durch Transformation auf Hermitesche Normalform und Überprüfung des Ergebnisses. Diplomarbeit, Martin-Luther-Univ. Halle-Wittenberg, Sektion Mathematik, Halle 1980, 72 pp.

    Google Scholar 

  48. Springer, J.: Exakte Rechnung durch Residuenarithmetik und einige Möglichkeiten ihrer Anwendung. Doctoral Dissertation, Martin-Luther-Univ. Halle-Wittenberg, Fak. für Naturwiss. d. Wiss. Rates. Halle 1982, 202 pp.

    Google Scholar 

  49. Springer, J.: Die exakte Berechnung der Moore-Penrose-Inversen einer Matrix durch Residuen-arithmetik. ZAMM63, 203–210 (1983).

    Google Scholar 

  50. Springer, J.: Exact solution of general integer systems of linear equations. ACM Trans. Math. Software (submitted).

  51. Stallings, W. T., Boullion, T. L.: Computation of pseudoinverse matrices using residue arithmetic. SIAM Review14, 152–163 (1972).

    Google Scholar 

  52. Stewart, G. W.: On the numerical properties of an iteration for computing the Moore-Penrose generalized inverse. Tech. Rep. CNA-12, Univ. of Texas at Austin, Center for Numerical Analysis, 1971, 27 pp.

  53. Stewart, G. W.: On the perturbation of pseudo-inverses, projections and linear least squares problems. SIAM Review19, 634–662 (1977).

    Google Scholar 

  54. Stewart, G. W.: The efficient generation of random orthogonal matrices with an application to condition estimates. SIAM J. Numer. Anal.17, 403–409 (1980).

    Google Scholar 

  55. Tanabe, K.: Conjugate-gradient method for computing the Moore-Penrose inverse and rank of a matrix. J. Optim. Theory Appl.22, 1–23 (1977).

    Google Scholar 

  56. Tautenhahn, U.: Zur Auswahl glatter Lösungen über der Lösungsmannigfaltigkeit unterbestimmter schlechtkonditionierter Systeme. Beiträge Numer. Math.10, 181–189 (1981).

    Google Scholar 

  57. Todd, J.: Basic numerical mathematics. Vol. 2: Numerical algebra. 216 pp. Basel-Stuttgart: Birkhäuser Verlag 1977.

    Google Scholar 

  58. Tsao, N.-K.: A note on implementing the Householder transformation. SIAM J. Numer. Anal.12, 53–58 (1975).

    Google Scholar 

  59. Turnovec, F.: Speciální matice pro konstrukci testovacích úloh. Ekonom.-Mat. Obzor15, 361–380 (1979).

    Google Scholar 

  60. Voevodin, V. V.: Rounding errors and stability in direct methods of linear algebra (Russian). 153 pp. Moscow: Moscow State Univ. 1969.

    Google Scholar 

  61. Voevodin, V. V.: Asymptotic perturbation theory in linear algebra problems (Russian). Vychisl. Metody i Programmirovanie, Vyp.26, 3–16 (1977).

    Google Scholar 

  62. Voevodin, V. V.: Basic concepts in numerical linear algebra (Russian). 304 pp. Moscow: Nauka 1977.

    Google Scholar 

  63. Wampler, R. H.: An evaluation of linear least squares computer programs. J. Res. Nat. Bur. Standards, Sect. B,73B, 59–90 (1969).

    Google Scholar 

  64. Wampler, R. H.: A report on the accuracy of some widely used least squares computer programs. J. Amer. Statist. Assoc.65, 549–565 (1970).

    Google Scholar 

  65. Wampler, R. H.: Some recent developments in linear least-squares computations. In: Proceedings of the Computer Science and Statistics Sixth Annual Symposium on the Interface (Tarter, M. E., ed.), pp. 94–110. Univ. of California, Berkeley, California, 1972.

    Google Scholar 

  66. Wampler, R. H.: WBASIC: A linear least squares program with iterative refinement. Statistical Engineering Laboratory, National Bureau of Standards, Washington, D.C., W-75-1, 1975, 39 pp.

  67. Wampler, R. H.: Problems used in testing the efficiency and accuracy of the modified Gram-Schmidt least squares algorithm. Technical Note 1126, National Bureau of Standards, Washington, D. C., U. S. Gov't Printing Office, 1980, 80 pp.

    Google Scholar 

  68. Wedin, P.-Å.: Perturbation theory for pseudo-inverses. BIT13, 217–232 (1973).

    Google Scholar 

  69. Westlake, J. R.: A handbook of numerical matrix inversion and solution of linear equations. 171 pp. New York-London-Sydney. Wiley & Sons 1968.

    Google Scholar 

  70. Wilkinson, J. H.: Rounding errors in algebraic processes. Information Processing. UNESCO, Paris; London: Butterworth 1960, pp. 44–53.

    Google Scholar 

  71. Wilkinson, J. H.: Error analysis of direct methods of matrix inversion. J. Assoc. Comput. Mach.8, 281–330 (1961).

    Google Scholar 

  72. Wilkinson, J. H.: Rounding errors in algebraic processes 161 pp. London: Her Majesty's Stationery Office; Englewood Cliffs, N.J.: Prentice-Hall 1963.

    Google Scholar 

  73. Wilkinson, J. H.: The algebraic eigenvalue problem. 662 pp. Oxford: Clarendon Press 1965.

    Google Scholar 

  74. Wilkinson, J. H.: Modern error analysis. SIAM Review13, 548–568 (1971).

    Google Scholar 

  75. Wilkinson, J. H., Reinsch, C. (eds.): Handbook for automatic computation. Vol. II: Linear algebra. 439 pp. Berlin: Springer-Verlag 1971.

    Google Scholar 

  76. Zielke, G.: Testmatrizen mit maximaler Konditionszahl. Computing13, 33–54 (1974).

    Google Scholar 

  77. Zielke, G.: Testmatrizen mit freien Parametern. Computing15, 87–103 (1975).

    Google Scholar 

  78. Zielke, G.: Beiträge zur Theorie und Berechnung von verallgemeinerten inversen Matrizen. Ph. D. Thesis, Martin-Luther-Univ. Halle-Wittenberg, Fak. f. Naturwiss. d. Wiss. Rates, Halle 1977, 325 pp.

    Google Scholar 

  79. Zielke, G.: Test matrices for generalized inverses. SIGNUM Newsletter13, No. 4, 10–12 (1978).

    Google Scholar 

  80. Zielke, G.: Motivation und Darstellung von verallgemeinerten Matrixinversen. Beiträge Numer. Math.7, 177–218 (1979).

    Google Scholar 

  81. Zielke, G.: Generalizations of a Rutishauser test matrix with exact Moore-Penrose inverses. SIGNUM Newsletter16, No. 3, 7–8 (1981). Errata: SIGNUM Newsletter16, No. 4, 6 (1981).

    Google Scholar 

  82. Zielke, G.: Verallgemeinerungen einer Testmatrix von Rutishauser mit exakten Moore-Penrose-Inversen. ZAMM61, 662–663 (1981).

    Google Scholar 

  83. Zielke, G.: A survey of generalized matrix inverses. Computational Mathematics, Banach Center Pub.13, 499–526 (1984).

    Google Scholar 

  84. Zlatev, Z., Schaumburg, K., Wasniewski, J.: A testing scheme for subroutines solving large linear problems. Computers & Chemistry5, 91–100 (1981).

    Google Scholar 

  85. Faddeeva, V. N., Kolotilina, L. Yu.: Computational methods of linear algebra. Collection of test matrices (Russian). Ed. V. V. Voevodin. Leningr. Otd. Mat. Inst. Akad. Nauk SSSR, Leningrad 1982, vol. 1, 131 pp.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Sektion Mathematik Martin-Luther-Universität Halle-Wittenberg, Weinbergweg 17, DDR-402, Halle, German Democratic Republic

    G. Zielke

Authors
  1. G. Zielke
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

In memory of Vera Nikolaevna Faddeeva, the great pioneer of numerical linear algebra († October 15, 1983)

Rights and permissions

Reprints and permissions

About this article

Cite this article

Zielke, G. Report on test matrices for generalized inverses. Computing 36, 105–162 (1986). https://doi.org/10.1007/BF02238196

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02238196

AMS Subject Classifications

Key words

Search

Navigation