×

A direct method for sparse least squares problems with lower and upper bounds. (English) Zbl 0659.65039

The least squares problem \(\| Ax-b\|_ 2\to Min\). (the solution of which being subject to the additional restriction \(1\leq x\leq u)\) is solved by QR-factorization (using SPARSEPAK), followed by a stable updating procedure for R. The main point is that the updating avoids fill-in and uses the fixed data structure of the factor R. Comparing numerical tests between the new method and the algorithm NNLS of C. L. Lawson and R. J. Hanson (Solving least squares problems. (1974; M.R. 51.2270)] show remarkable savings both in CPU-time and in storage requirements.
Reviewer: G.Maeß

MSC:

65F20 Numerical solutions to overdetermined systems, pseudoinverses
65F05 Direct numerical methods for linear systems and matrix inversion

Software:

SPARSPAK; symrcm; LINPACK

References:

[1] Bartels, R.: Constrained least squares, quadratic programming, complementary pivot programming and duality. In: Proceedings of Computer Science and Statistics 8th Annual Symposium on the Interface 1975
[2] Björck, Å.: Stability analysis of the method of semi-normal-equations for linear least squares problems. Linear Algebra Appl.88/89, 31-48 (1987) · Zbl 0616.65043 · doi:10.1016/0024-3795(87)90101-7
[3] Björck, Å.: Least squares methods. In: Handbook of Numerical Analysis, Vol. II. (P.G. Ciarlet, J.L. Lions, eds.). Amsterdam New York: Elsevier/North-Holland 1988 (in press) · Zbl 0659.65039
[4] Coleman, T.F., Edenbrandt, A., Gilbert, J.R.: Predicting fill for sparse orthogonal factorization. J. ACM33, 517-532 (1983) · Zbl 0635.65036 · doi:10.1145/5925.5932
[5] Cottle, R.W., Golub, G.H., Sacher, R.S.: On the solution of large structured linear complementarity problems: The block partitioned case. Appl. Math. Optimization4, 347-363 (1978) · Zbl 0391.90087 · doi:10.1007/BF01442149
[6] Cryer, C.W.: The solution of a quadratic programming problem using systematic overrelaxation. J. SIAM Control9, 385-392 (1971) · Zbl 0216.54603 · doi:10.1137/0309028
[7] Dongarra, J., Bunch, J.R., Moler, C.B., Stewart, G.W.: LINPACK User’s Guide. 1st Ed. SIAM Publications, Philadelphia 1979 · Zbl 0476.68025
[8] Foster, L.V.: Rank and nullspace calculations using matrix decompositions without column interchanges. Linear Algebra Applics.74, 47-71 (1986) · Zbl 0589.65031 · doi:10.1016/0024-3795(86)90115-1
[9] George, A., Heath, M.T.: Solution of sparse linear least squares problem using Givens rotations. Linear Algebra Appl.34, 69-83 (1980) · Zbl 0459.65025 · doi:10.1016/0024-3795(80)90159-7
[10] George, A., Liu, J.W.: Computer Solution of Large Sparse Positive Definite Systems, 1st Ed. Prentice-Hall, Englewood Cliffs, N.J. 1981 · Zbl 0516.65010
[11] George, A., Ng, E.: On row and column orderings for sparse least squares problems. SIAM J. Numer. Anal.20, 326-344 (1983) · Zbl 0513.65019 · doi:10.1137/0720022
[12] George, A., Ng. E.: SPARSPAK: Waterloo Sparse Matrix Package User’s Guide for SPARSPAKB. Report CS-84-37, Department of Computer Science, University of Waterloo, November 1984
[13] Gill, P.E., Golub, G.H., Murray, W., Saunders, M.A.: Methods for modifying matrix factorizations. Math. Comput.28, 505-535 (1974) · Zbl 0289.65021 · doi:10.1090/S0025-5718-1974-0343558-6
[14] Gill, P.E., Murray, W., Wright, M.H.: Practical Optimization, 1st Ed. New York London: Academic Press 1981 · Zbl 0503.90062
[15] Gill, P.E., Murray, W., Saunders, M.A., Wright, M.: Sparse matrix methods in optimization. SIAM J. Sci. Stat. Comput.5, 562-589 (1984) · Zbl 0559.65042 · doi:10.1137/0905041
[16] Haskell, K.H., Hanson, R.J.: An algorithm for linear least squares problems with equality and nonnegativity constraints. Math. Program.21, 98-118 (1981) · Zbl 0461.90056 · doi:10.1007/BF01584232
[17] Heath, M.T.: Some extensions of an algorithm for sparse linear least squares problems. SIAM J. Sci. Stat. Comput.3, 223-237 (1982) · Zbl 0483.65027 · doi:10.1137/0903014
[18] Heath, M.T.: Numerical methods for large sparse linear least squares problems. SIAM J. Sci. Stat. Comput.5, 497-513 (1984) · Zbl 0575.65030 · doi:10.1137/0905037
[19] Lawson, C.L., Hanson, R.J.: Solving Least Squares Problems, 1st Ed. Englewood Cliffs NJ, Prentice-Hall 1974 · Zbl 0860.65028
[20] Lötstedt, P.: Solving the minimal least squares problem subject to bounds on the variables. BIT24, 206-224 (1984) · Zbl 0546.65041 · doi:10.1007/BF01937487
[21] O’Leary, D.P.: A generalized conjugate gradient algorithm for solving a class of quadratic programming problems. Linear Algebra Appl.34, 371-399 (1980) · Zbl 0464.65039 · doi:10.1016/0024-3795(80)90173-1
[22] Oreborn, U.: A direct method for sparse nonnegative least squares problems, Linköping Studies in Science and Technology, Lic. Thesis No. 87, Linköping University, Sweden 1986
[23] Rice, J.R.: PARVEC workshop on very large least squares problems and supercomputers, Report CSD-TR 464, Purdue University 1983
[24] Schittkowski, K., Stoer, J.: A factorization method for the solution of constrained linear least squares problems allowing subsequent data changes. Nume. Math.31, 431-463 (1979) · Zbl 0378.65026 · doi:10.1007/BF01404569
[25] Stewart, G.W.: Perturbation bounds for the QR factorization of a matrix. SIAM J. Numer. Anal.3, 509-518 (1977) · Zbl 0358.65038 · doi:10.1137/0714030
[26] Stoer, J.: On the numerical solution of constrained least squares problems. SIAM J. Numer. Anal.8, 382-411 (1971) · Zbl 0219.90039 · doi:10.1137/0708038
[27] Zimmermann, P.: Ein Algorithmus zur Lösung Linearer Least-Squares-Probleme mit unteren und oberen Schranken als Nebenbedingungen (Diplomarbeit), Julius-Maximilian-Universität, Würzburg 1977
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.