Report on test matrices for generalized inverses. (English) Zbl 0566.65026
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 order n, sets of \(7\times 6\) and \(7\times 5\) matrices of different rank, a set of \(5\times 5\) matrices which are equal to their Moore-Penrose inverse and some special test matrices known from literature. For the set of \(7\times 6\) parameter matrices also the singular values corresponding to six values of the parameter are listed. For three simple parameter matrices of order \(5\times 4\) and \(6\times 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.
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.
MSC:
| 65F20 | Numerical solutions to overdetermined systems, pseudoinverses |
| 15A09 | Theory of matrix inversion and generalized inverses |
| 65F25 | Orthogonalization in numerical linear algebra |
| 65F35 | Numerical computation of matrix norms, conditioning, scaling |
| 15B57 | Hermitian, skew-Hermitian, and related matrices |
Keywords:
test matrices; generalized inverses; Moore-Penrose inverse; linear least squares; singular values; condition numbers; unitary matrices; orthogonal matrices; column-orthogonal matrices; row-orthogonal matrices; involutary matrix; Hadamard matricesReferences:
| [1] | Abdelmalek, N. N.: Round off error analysis for Gram-Schmidt method and solution of linear least squares problems. BIT11, 345–367 (1971). · Zbl 0236.65031 · doi:10.1007/BF01939404 |
| [2] | Abdelmalek, N. N.: On the solution of the linear least squares problems and pseudo-inverses. Computing13, 215–228 (1974). · Zbl 0333.65017 · doi:10.1007/BF02241714 |
| [3] | Bellman, R.: Introduction to matrix analysis. 328 pp. New York-Toronto-London: McGraw-Hill 1960. · Zbl 0124.01001 |
| [4] | Ben-Israel, A., Greville, T. N. E.: Generalized inverses: Theory and applications. 395 pp. New York: Wiley-Interscience 1974. · Zbl 0305.15001 |
| [5] | Berman, A.: Nonnegative matrices which are equal to their generalized inverse. Linear Algebra Appl.9, 261–265 (1974). · Zbl 0312.15009 · doi:10.1016/0024-3795(74)90042-1 |
| [6] | Björck, Å.: Solving linear least squares problems by Gram-Schmidt orthogonalization. BIT7, 1–21 (1967). · Zbl 0183.17802 · doi:10.1007/BF01934122 |
| [7] | Björck, Å., Golub, G.: Iterative refinement of linear least squares solutions by Householder transformation. BIT7, 322–337 (1967). · doi:10.1007/BF01939326 |
| [8] | Campbell, S. L., Meyer, C. D. Jr.: Generalized inverses of linear transformations. 272 pp. London-San Francisco-Melbourne: Pitman 1979. · Zbl 0417.15002 |
| [9] | Deuflhard, P., Sautter, W.: On rank-deficient pseudoinverses. Linear Algebra Appl.29, 91–111 (1980). · Zbl 0452.65019 · doi:10.1016/0024-3795(80)90232-3 |
| [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. |
| [11] | Faddeev, D. K., Faddeeva, V. N.: Computational methods of linear algebra. 621 pp. San Francisco: Freeman & Co. 1963. · Zbl 0112.07503 |
| [12] | Forsythe, G. E., Moler, C. B.: Computer solution of linear algebraic systems. 148 pp. Englewood Cliffs, N.J.: Prentice-Hall 1967. · Zbl 0154.40401 |
| [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. · Zbl 0055.35005 |
| [14] | Goldstine, H. H., von Neumann, J.: Numerical inverting of matrices of high order. II. Proc. Amer. Math. Soc.2, 188–202 (1951). · Zbl 0043.12301 · doi:10.1090/S0002-9939-1951-0041539-X |
| [15] | Golub, G., Kahan, W.: Calculating the singular values and pseudo-inverse of a matrix. SIAM J. Numer. Anal.2, 205–224 (1965). · Zbl 0194.18201 |
| [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. |
| [17] | Golub, G. H., Reinsch, C.: Singular value decomposition and least squares solutions. Numer. Math.14, 403–420 (1970). Also in [75]. 134–151. · Zbl 0181.17602 · doi:10.1007/BF02163027 |
| [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. · Zbl 0195.44803 |
| [19] | Gröbner, W.: Matrizenrechnung. 279 pp. Mannheim-Wien-Zürich: Bibliographisches Institut 1966. |
| [20] | Householder, A. S.: The theory of matrices in numerical analysis. 257 pp. New York-Toronto-London: Blaisdell 1964. · Zbl 0161.12101 |
| [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). · doi:10.1016/0165-1765(79)90203-9 |
| [22] | Kymn, K. O., Norsworthy, J. R., Okamoto, T.: The computation of the generalized inverse. Kyungpook Math. J.20, 199–206 (1980). · Zbl 0455.65030 |
| [23] | Lawson, C. L., Hanson, R. J.: Solving least squares problems. 340 pp. Englewood Cliffs, N.J.: Prentice-Hall 1974. |
| [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). · doi:10.2307/2283673 |
| [25] | Mirsky, L.: An introduction to linear algebra. 433 pp. London: Oxford Univ. Press 1955. · Zbl 0066.26305 |
| [26] | Moore, E. H.: On the reciprocal of the general algebraic matrix (Abstract). Bull. Amer. Math. Soc.26, 394–395 (1920). |
| [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). · Zbl 0031.31402 · doi:10.1090/S0002-9904-1947-08909-6 |
| [29] | Newman, M., Todd, J.: The evaluation of matrix inversion programs. J. Soc. Indust. Appl. Math.6, 466–476 (1958). · Zbl 0085.34305 · doi:10.1137/0106030 |
| [30] | Noble, B.: A method for computing the generalized inverse of a matrix. SIAM J. Numer. Anal.3, 582–584 (1966). · Zbl 0147.13105 · doi:10.1137/0703049 |
| [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. · Zbl 0347.65023 |
| [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. |
| [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). · Zbl 0478.65016 · doi:10.1145/355984.355989 |
| [34] | Penrose, R.: A generalized inverse for matrices. Proc. Cambridge Philos. Soc.51, 406–413 (1955). · Zbl 0065.24603 · doi:10.1017/S0305004100030401 |
| [35] | Penrose, R.: On best approximate solutions of linear matrix equations. Proc. Cambridge Philos. Soc.52, 17–19 (1956). · Zbl 0070.12501 · doi:10.1017/S0305004100030929 |
| [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. |
| [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). · Zbl 0328.65026 · doi:10.1137/0713017 |
| [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. |
| [39] | Rutishauser, H.: Once again: the least square problem. Linear Algebra Appl.1, 479–488 (1968). · Zbl 0169.19502 · doi:10.1016/0024-3795(68)90022-0 |
| [40] | Sautter, W.: Fehlerfortpflanzung und Rundungsfehler bei der verallgemeinerten Inversion von Matrizen. Doctoral Dissertation, TU München, München 1971, 85 pp. |
| [41] | Sautter, W.: Fehleranalyse für die Gauß-Elimination zur Berechnung der Lösung minimaler Länge. Numer. Math.30, 165–184 (1978). · Zbl 0425.65024 · doi:10.1007/BF02042943 |
| [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). · Zbl 0315.65027 · doi:10.1007/BF02479751 |
| [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). · Zbl 0302.65031 · doi:10.1090/S0025-5718-1975-0368407-2 |
| [44] | Van der Sluis, A.: Stability of the solutions of linear least squares problems. Numer. Math.23, 241–254 (1975). · Zbl 0308.65026 |
| [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). |
| [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). · doi:10.1137/0711008 |
| [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. |
| [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. |
| [49] | Springer, J.: Die exakte Berechnung der Moore-Penrose-Inversen einer Matrix durch Residuen-arithmetik. ZAMM63, 203–210 (1983). · Zbl 0532.65024 · doi:10.1002/zamm.19830630308 |
| [50] | Springer, J.: Exact solution of general integer systems of linear equations. ACM Trans. Math. Software (submitted). · Zbl 0594.65029 |
| [51] | Stallings, W. T., Boullion, T. L.: Computation of pseudoinverse matrices using residue arithmetic. SIAM Review14, 152–163 (1972). · Zbl 0238.65016 · doi:10.1137/1014005 |
| [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). · Zbl 0379.65021 · doi:10.1137/1019104 |
| [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). · Zbl 0443.65027 · doi:10.1137/0717034 |
| [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). · Zbl 0336.65023 · doi:10.1007/BF00936715 |
| [56] | Tautenhahn, U.: Zur Auswahl glatter Lösungen über der Lösungsmannigfaltigkeit unterbestimmter schlechtkonditionierter Systeme. Beiträge Numer. Math.10, 181–189 (1981). · Zbl 0467.65019 |
| [57] | Todd, J.: Basic numerical mathematics. Vol. 2: Numerical algebra. 216 pp. Basel-Stuttgart: Birkhäuser Verlag 1977. |
| [58] | Tsao, N.-K.: A note on implementing the Householder transformation. SIAM J. Numer. Anal.12, 53–58 (1975). · doi:10.1137/0712005 |
| [59] | Turnovec, F.: Speciální matice pro konstrukci testovacích úloh. Ekonom.-Mat. Obzor15, 361–380 (1979). |
| [60] | Voevodin, V. V.: Rounding errors and stability in direct methods of linear algebra (Russian). 153 pp. Moscow: Moscow State Univ. 1969. |
| [61] | Voevodin, V. V.: Asymptotic perturbation theory in linear algebra problems (Russian). Vychisl. Metody i Programmirovanie, Vyp.26, 3–16 (1977). |
| [62] | Voevodin, V. V.: Basic concepts in numerical linear algebra (Russian). 304 pp. Moscow: Nauka 1977. |
| [63] | Wampler, R. H.: An evaluation of linear least squares computer programs. J. Res. Nat. Bur. Standards, Sect. B,73B, 59–90 (1969). · Zbl 0176.47402 |
| [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). · Zbl 0196.22405 · doi:10.2307/2284566 |
| [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. |
| [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. · Zbl 0434.65022 |
| [68] | Wedin, P.-Å.: Perturbation theory for pseudo-inverses. BIT13, 217–232 (1973). · Zbl 0263.65047 · doi:10.1007/BF01933494 |
| [69] | Westlake, J. R.: A handbook of numerical matrix inversion and solution of linear equations. 171 pp. New York-London-Sydney. Wiley & Sons 1968. · Zbl 0155.19901 |
| [70] | Wilkinson, J. H.: Rounding errors in algebraic processes. Information Processing. UNESCO, Paris; London: Butterworth 1960, pp. 44–53. · Zbl 0113.10606 |
| [71] | Wilkinson, J. H.: Error analysis of direct methods of matrix inversion. J. Assoc. Comput. Mach.8, 281–330 (1961). · Zbl 0109.09005 |
| [72] | Wilkinson, J. H.: Rounding errors in algebraic processes 161 pp. London: Her Majesty’s Stationery Office; Englewood Cliffs, N.J.: Prentice-Hall 1963. |
| [73] | Wilkinson, J. H.: The algebraic eigenvalue problem. 662 pp. Oxford: Clarendon Press 1965. · Zbl 0258.65037 |
| [74] | Wilkinson, J. H.: Modern error analysis. SIAM Review13, 548–568 (1971). · Zbl 0243.65018 · doi:10.1137/1013095 |
| [75] | Wilkinson, J. H., Reinsch, C. (eds.): Handbook for automatic computation. Vol. II: Linear algebra. 439 pp. Berlin: Springer-Verlag 1971. · Zbl 0219.65001 |
| [76] | Zielke, G.: Testmatrizen mit maximaler Konditionszahl. Computing13, 33–54 (1974). · Zbl 0282.65032 · doi:10.1007/BF02268390 |
| [77] | Zielke, G.: Testmatrizen mit freien Parametern. Computing15, 87–103 (1975). · Zbl 0311.65025 · doi:10.1007/BF02252859 |
| [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. |
| [79] | Zielke, G.: Test matrices for generalized inverses. SIGNUM Newsletter13, No. 4, 10–12 (1978). · doi:10.1145/1053412.1053415 |
| [80] | Zielke, G.: Motivation und Darstellung von verallgemeinerten Matrixinversen. Beiträge Numer. Math.7, 177–218 (1979). · Zbl 0408.15003 |
| [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). · doi:10.1145/1057578.1057579 |
| [82] | Zielke, G.: Verallgemeinerungen einer Testmatrix von Rutishauser mit exakten Moore-Penrose-Inversen. ZAMM61, 662–663 (1981). · Zbl 0513.65021 · doi:10.1002/zamm.19810611211 |
| [83] | Zielke, G.: A survey of generalized matrix inverses. Computational Mathematics, Banach Center Pub.13, 499–526 (1984). · Zbl 0572.65026 |
| [84] | Zlatev, Z., Schaumburg, K., Wasniewski, J.: A testing scheme for subroutines solving large linear problems. Computers & Chemistry5, 91–100 (1981). · Zbl 0461.65023 · doi:10.1016/0097-8485(81)80014-9 |
| [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. · Zbl 0533.65012 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
