Algorithm 741: least-squares solution of a linear, bordered, block-diagonal system of equations

ABSTRACT

A package of Fortran subroutines is presented for the least-squares solution of a system of overdetermined, full-rank, linear equations with single-bordered block-diagonal structure. This structure allows for a natural sequential processing, one block diagonal at a time, so that large systems can be handled even on smaller machines. Orthogonal transformations in the form of Householder reflections are used to factor the system. The routines make heavy use of the Levels 1, 2, and 3 BLAS.

REFERENCES

• 1: ANDERLE, R. J. 1974. Transformation of terrestrial survey data to Doppler satellite datum. J. Geophys Res. 79, 35 (Dec.), 5319-5331.
• 2: E. Anderson , Z. Bai , C. Bischof , J. Demmel , J. Dongarra , J. Du Croz , A. Greenbaum , S. Hammarling , A. McKenney , S. Ostrouchov , D. Sorensen, LAPACK's user's guide, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 3: Thomas F. Coleman, Large sparse numerical optimization, Springer-Verlag New York, Inc., New York, NY, 1984
• 4: Jack J. Dongarra , Jeremy Du Croz , Sven Hammarling , Richard J. Hanson, An extended set of FORTRAN basic linear algebra subprograms, ACM Transactions on Mathematical Software (TOMS), v.14 n.1, p.1-17, March 1988 [doi>10.1145/42288.42291]
• 5: J. J. Dongarra , Jeremy Du Croz , Sven Hammarling , I. S. Duff, A set of level 3 basic linear algebra subprograms, ACM Transactions on Mathematical Software (TOMS), v.16 n.1, p.1-17, March 1990 [doi>10.1145/77626.79170]
• 6: GEORGE, A., HEATH, M. T., AND PLEMMONS, R. J. 1981. Solution of large-scale sparse least squares problems using auxiliary storage. SIAM J. Sci. Star. Comput. 2, 4 (Dec.), 416-429.
• 7: GOLUB, G. H. AND PLEMMONS, R. J. 1980. Large-scale geodetic least-squares adjustment by dissection and orthogonal decomposition. Lin. Alg. Appl. 34, 3, 3-27.
• 8: R. J. Hanson , F. T. Krogh, ALGORITHM 653: translation of algorithm 539: PC-BLAS, basic linear algebra subprograms for FORTRAN usage with the INTEL 8087, 80287 numeric data processor, ACM Transactions on Mathematical Software (TOMS), v.13 n.3, p.311-317, Sept. 1987 [doi>10.1145/29380.214346]
• 9: HEATH, M. T. 1984. Numerical methods for large sparse linear least squares problems. SIAM J. Sci. Stat. Comput. 5, 3 (Sept.), 497-513.
• 10: LANGEL, R. A., ESTES, R. H., AND MEAD, G. D. 1982. Some new methods in geomagnetic field modeling applied to the 1960-1980 epoch. J. Geomagn. Geoelec. 34, 6, 327-349.
• 11: LAWSON, C. L. AND HANSEN, R. J. 1974. Solving Least Squares Problems. Prentice-Hall, Englewood Cliffs, N.J.
• 12: 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]
• 13: MA, C., SAUBER, J. M., BELL, L. J., CLARK, T. A., GORDAN, D., HIMWICH, W. E., AND RYAN, J. W. 1990. Measurement of horizontal motions in Alaska using very long baseline interferometry. J. Geophys. Res. 95, B13 (Dec.), 21991-22011.
• 14: RAY, R. D. AND KOBLINSKY, C. J. 1991. On the sea-state bias of the Geosat altimeter. J. Atmos. Ocean. Tech. 8, 3 (June), 397-408.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Linear systems (direct and iterative methods)

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Least squares methods

General Terms:
Algorithms

Keywords:
bordered block-diagonal equations, least-squares solutions, sparse systems