×
Ikramov, Kh. D.

Sparse linear problems and the least squares method. (English. Russian original) Zbl 0656.65042

J. Sov. Math. 39, No. 6, 3148-3189 (1987); translation from Itogi Nauki Tekh., Ser. Mat. Anal. 23, 219-285 (1985).
See the review in Zbl 0638.65032.

MSC:

65F20 Numerical solutions to overdetermined systems, pseudoinverses
15A09 Theory of matrix inversion and generalized inverses
65F50 Computational methods for sparse matrices

Keywords:

least squares problem; block orthogonal methods; numerical results; covariance matrix

Citations:

Zbl 0329.65026; Zbl 0351.65004; Zbl 0459.65025; Zbl 0469.65021; Zbl 0638.65032

Software:

symrcm
Cite Review PDF
Full Text: DOI

References:

[1] V. V. Voevodin, Linear Algebra [in Russian], Nauka, Moscow (1974).
[2] V. V. Voevodin, Numerical Foundations of Linear Algebra [in Russian], Nauka, Moscow (1977). · Zbl 0563.65010
[3] A. George and J. W. Liu, Computer Solution of Large Sparse Positive-Definite Systems, Prentice-Hall, Englewood Cliffs (1981). · Zbl 0516.65010
[4] B. N. Parlett, The Symmetric Eigenvalue Problem, Prentice-Hall, Englewood Cliffs (1980). · Zbl 0431.65017
[5] J. H. Wilkinson, The Algebraic Eigenvalue Problem, Clarendon Press, Oxford (1965). · Zbl 0258.65037
[6] J. O. Aasen, ?On the reduction of a symmetric matrix to tridiagonal form,? BIT,11, No. 3, 233?242 (1971). · Zbl 0242.65032 · doi:10.1007/BF01931804
[7] V. Ashkenazi, ?Geodetic normal equations,? in: Large Sparse Sets of Linear Equations (ed. J. K. Reid), Academic Press, New York (1971), pp. 57?74.
[8] N. Åslund, ?A data processing system for spectra of diatomic molecules,? Ark. Fysik,30, 377?396 (1965).
[9] J. K. Avila and J. A. Tomlin, ?Solution of very large least squares problems by nested dissection on a parallel processor,? in: Proceedings of Computer Science and Statistics: Twelfth Annual Symposium on the Inferface, Waterloo, Canada (1979).
[10] A. Björck, ?Solving linear least squares problems by Gram-Schmidt orthogonalization,? BIT,7, 1?21 (1967). · Zbl 0183.17802 · doi:10.1007/BF01934122
[11] A. Björck, ?Iterative refinement of linear least squares solutions. I,? BIT,7, No. 4, 257?278 (1967). · Zbl 0159.20404 · doi:10.1007/BF01939321
[12] A. Björck, ?Methods for sparse linear least squares problems,? in: Sparse Matrix Computations (J. Bunch and D. Rose, eds.), Academic Press, New York (1976), pp. 177?199.
[13] A. Björck, ?Comment on the iterative refinement of least squares solutions,? J. Am. Statist. Assoc.,73, No. 361, 161?166 (1978).
[14] A. Björck, Least Squares Methods in Physics and Engineering, CERN, Geneva (1981).
[15] A. Björck and I. S. Duff, ?A direct method for the solution of sparse linear least squares problems,? Linear Algebra Appl.,34, 43?67 (1980). · Zbl 0471.65021 · doi:10.1016/0024-3795(80)90158-5
[16] A. Björck and G. H. Golub, ?Iterative refinement of linear least squares solutions by Householder transformations,? BIT,7, 322?337 (1967). · doi:10.1007/BF01939326
[17] J. R. Bunch and L. Kaufman, ?Some stable methods for calculating inertia and solving symmetric linear systems,? Math. Comp.,31, No. 137, 163?179 (1977). · Zbl 0355.65023 · doi:10.1090/S0025-5718-1977-0428694-0
[18] P. A. Businger and G. H. Golub, ?Linear least squares solutions by Householder transformations,? Numer. Math.,7, 269?276 (1965). · Zbl 0142.11503 · doi:10.1007/BF01436084
[19] A. R. Curtis and J. K. Reid, ?The solution of large sparse unsymmetric systems of linear equations,? J. Inst. Math. Appl.,8, 344?353 (1971). · Zbl 0229.65032 · doi:10.1093/imamat/8.3.344
[20] A. Dax, ?Partial pivoting strategies for symmetric Gaussian elimination,? Math. Programming,22, 288?303 (1982). · Zbl 0476.90039 · doi:10.1007/BF01581044
[21] I. S. Duff, ?Pivot selection and row ordering in Givens reduction on sparse matrices,? Computing,13, 239?248 (1974). · Zbl 0298.65029 · doi:10.1007/BF02241717
[22] I. S. Duff, ?A survey of sparse matrix research,? Proc. IEEE,65, No. 4, 500?535 (1977). · doi:10.1109/PROC.1977.10514
[23] I. S. Duff and J. K. Reid, ?A comparison of some methods for the solution of sparse overdetermined systems of linear equations,? J. Inst. Math. Appl.,17, No. 3, 267?280 (1976). · Zbl 0329.65026 · doi:10.1093/imamat/17.3.267
[24] W. M. Gentleman, ?Regression problems and the QR-decomposition,? Bull. Inst. Math. Appl.,10, 195?197 (1974).
[25] W. M. Gentleman, ?Row elimination for solving sparse linear systems and least squares problems,? Lect. Notes Math., No. 506, 122?133 (1976). · Zbl 0334.65032 · doi:10.1007/BFb0080119
[26] A. George and M. T. Heath, ?Solution of sparse linear least squares problems using Givens rotations,? Linear Algebra Appl.,34, 69?83 (1980). · Zbl 0459.65025 · doi:10.1016/0024-3795(80)90159-7
[27] A. George, M. T. Heath, and R. J. Plemmons, ?Solution of large-scale sparse least squares problems using auxiliary storage,? SIAM J. Sci. Statist. Comput.,2, No. 4, 416?429 (1981). · Zbl 0469.65021 · doi:10.1137/0902034
[28] A. George and E. Ng, ?On row and column orderings for sparse least squares problems,? SIAM J. Numer. Anal.,20, No. 2, 326?344 (1983). · Zbl 0513.65019 · doi:10.1137/0720022
[29] A. George, W. G. Poole, Jr., and R. G. Voigt, ?Incomplete nested dissection for solving n by n grid problems,? SIAM J. Numer. Anal.,15, No. 4, 662?673 (1978). · Zbl 0393.65014 · doi:10.1137/0715044
[30] G. H. Glaser and M. S. Saliba, ?Application of sparse matrices to analytical photogrammetry,? in: Sparse Matrices and Their Applications (D. J. Rose and R. A. Willoughby, eds.), Plenum Press, New York (1972), pp. 135?146.
[31] G. H. Golub, ?Numerical methods for solving linear least squares problems,? Numer. Math.,7, 206?216 (1965). · Zbl 0142.11502 · doi:10.1007/BF01436075
[32] G. H. Golub and R. J. Plemmons, ?Large-scale geodetic least-squares adjustment by dissection and orthogonal decomposition,? Linear Algebra Appl.,34, 3?28 (1980). · Zbl 0468.65012 · doi:10.1016/0024-3795(80)90156-1
[33] M. T. Heath, ?Some extensions of an algorithm for sparse linear least squares problems,? SIAM J. Sci. Statist. Comput.,3, No. 2, 223?237 (1982). · Zbl 0483.65027 · doi:10.1137/0903014
[34] F. R. Helmert, Die Mathematischen und Physikalischen Theorien der Höheren Geodäsie, Teil I, Leipzig (1880). · JFM 16.1080.01
[35] Th. Lunde Johnsen and J. R. Roy, ?On systems of linear equations of the form ATAx=b; error analysis and certain consequences for structural applications,? Comput. Methods Appl. Mech. Eng.,3, No. 3, 357?374 (1974). · Zbl 0278.65032 · doi:10.1016/0045-7825(74)90020-6
[36] G. B. Kolata, ?Geodesy: dealing with an enormous computer task,? Science,200, 421?422 and 466 (1978). · doi:10.1126/science.200.4340.421
[37] C. L. Lawson and R. J. Hanson, Solving Least Squares Problems, Prentice-Hall, Englewood Cliffs, N.J. (1974). · Zbl 0860.65028
[38] G. Peters and J. H. Wilkinson, ?The least squares problem and pseudoinverses,? Comput. J.,13, 309?316 (1970). · Zbl 0195.44804 · doi:10.1093/comjnl/13.3.309
[39] D. J. Rose and R. E. Tarjan, ?Algorithmic aspects of vertex elimination on directed graphs,? SIAM J. Appl. Math.,34, 176?197 (1978). · Zbl 0377.65013 · doi:10.1137/0134014
[40] D. J. Rose, R. E. Tarjan, and G. S. Lueker, ?Algorithmic aspects of vertex elimination on graphs,? SIAM J. Comput.,5, No. 2, 266?283 (1976). · Zbl 0353.65019 · doi:10.1137/0205021
[41] R. A. Willoughby, ?Sparse matrix algorithms and their relation to problem classes and computer architecture,? in: Large Sparse Sets of Linear Equations (ed. J. K. Reid), Academic Press, New York (1971), pp. 255?277.
[42] Z. Zlatev, ?Comparison of two pivotal strategies in sparse plane rotations,? Comput. Math. Appl.,8, No. 2, 119?135 (1982). · Zbl 0485.65031 · doi:10.1016/0898-1221(82)90051-7
[43] Z. Zlatev, K. Schaumburg, and J. Wasniewski, ?Implementation of an iterative refinement option in a code for large and sparse systems,? Comput. Chem.,4, 87?99 (1980). · Zbl 0434.65050 · doi:10.1016/0097-8485(80)80007-6
[44] Z. Zlatev, J. Wasniewski, and K. Schaumburg, ?Y1M. Solution of large and sparse systems of linear algebraic equations. Documentation of subroutines,? Lect. Notes Comput. Sci., No. 121, Springer, Berlin (1981). · Zbl 0461.65023
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.