Design and implementation of a very small linear algebra program package

ABSTRACT

Microcomputers, when properly programmed, have sufficient memory and speed to successfully perform serious calculations of modest size--linear equations, least squares, matrix inverse or generalized inverse, and the symmetric matrix eigenproblem.

REFERENCES

• 1: Adler. A. Matrix inversion. Interface Age 4, 11 (Nov. 1979). 30-36. A discussion of matrix methods sadly dated even when published.
• 2: Bates. D.M.. and Watts. D.G. A relative offset orthogonality convergence criterion for nonlinear least squares. Technometrics 23. 2 (May 1981). 179-163. A discussion of the difficulties that arise in deciding when an iterative nonlinear least squares algorithm can no longer make meaningful progress toward a solution. A test criterion that can be computed with comparatively simple program code is suggested.
• 3: Dongarra, J.J., Bunch, J.R.. Moler. C.B., and Stewart, G.W. LINPACK User's Guide. Society for Industrial and Applied Mathematics, Philadelphia, Pa.. 1979. Documenation and exam&s of the use of the LINPACK collection of linear algebra prog&s. which are written in FORTRAN.
• 4: Draper. N.. and Smith, H. Applied regression analysis. 2nd ed. Wiley-Interscience. New York, 1981. A classic textbook and reference on regression analysis.
• 5: George E. Forsythe , Michael A. Malcolm , Cleve B. Moler, Computer Methods for Mathematical Computations, Prentice Hall Professional Technical Reference, 1977
• 6: Garbow. B.S.. et al. Matrix Eigensystems Routines-EISPACK Guide E.rtu~sio~~. Springer-Verlag. New York. 1977. Documentation of the FORTRAN programs for matrix eigenvalue problems in the EISPACK collection.
• 7: Golub. G.H.. and Van Loan, CF. Matrix Compulations. Johns Hopkins Univ. Press. Baltimore, Md.. 1963. An up-to-date and detailed survey of numerical methods for linear algebra. Extensive literature coverage is one of the virtues of this important book.
• 8: Marquardt. D.W. An algorithm for least squares estimation of nonlinear parameters. J. Sot. Ind. Appl. Math. II (19633, 431-441. Probably the most successful simple approach to nonlinear least squares in described in this paper. Many papers have been published suggesting "improvements." but some of these reflect poor programming practice in implementing Marquardt's ideas. Reference 9 discusses some of these misdirected criticisms of Marquardt's algorithm.
• 9: Nash, J.C. Compacr Numerical Methods for Compurers: Linear Algebra and Function Minimization. John Wiley, New York, 1979. A discussion of problem types arising in the natural and social sciences that can be solved by linear algebra and function minimization methods. Step-and-description algorithms suitable for rapid implementation are included.
• 10: Nash J.C. Generalized inverse matrices: A practical tool for matrix methods on microcomputers. Interface Age 5, 9 (Sept. 1960). 32-37. A description of the first version of the package descfibed in this paper, mainly directed at unsophisticated users. Listings are included but so photoreduced that readers have had difficulties implementing the code from a keyboard.
• 11: Nash, J.C.. and Shlien, S. Simple algorithms for the partial singular value decomposition. Work. Paper 83-27. Faculty of Administration, Univ. of Ottawa, Ontario. This paper, submitted for more general publication, includes a step-and-description algorithm of the streamlined singular value decomposition used in the package described in this paper.
• 12: Nash, J.C. LEQBO5 Documenfafion. Nash Information Services, Inc., Ottawa, Ontario, 1984. Documentation and source code of the package described in this paper.
• 13: Rosenbrock, H.H. An automatic method for finding the greatest or least value of a function. Comput. 1. 3. 3 (1960). 175-164. One of the earliest direct search methods for automatic function minimization.
• 14: Strang, G. Linear Algebra and its Applications. 2nd ed. Academic Press, New York, A modern textbook on linear algebra.
• 15: Wilkinson, J.H., and Reinsch. C., Eds. Handbookfor Automatic Conrpufation. Vol. 2. Linear Algebra. Springer-Verlag. New York, 1971. The "New Testament" of numerical linear algebra. incorporating ALGOL versions of many important methods for matrix computations.

INDEX TERMS

Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

General Terms:
Algorithms, Design, Performance