What is Numerical Linear Algebra?
by Ed Angel
One of the fundamental topics in linear algebra concerns sets of linear equations. In matrix form, we can write N equations in M variables as
Ax=y
where A is an n x m matrix of numbers, y is an n x 1 matrix of known values and x is an m x 1 matrix of the unknowns. In electrical engineering, A can describe a circuit of resistors, capacitors and inductors, y contains the values of voltage sources and the unknowns in x are the internal voltages. In civil and mechanical engineering, A describes the structure, whereas x and y represent internal and external forces, respectively. In both these examples, we might have millions of equations for designing computer processors or a large building.
Methods for solving such sets of equations with a small number of equations date back over 2000 years, and the resulting method is now known as Gaussian elimination. It is based on the idea that if we start with one equation, we can solve it for one of the variables. Then we can substitute this result into the rest of the equations, leaving us with one fewer equation and one fewer unknown. We can repeat this process multiple times until we are left with one equation in one unknown. Then, we can go backwards, each time getting the solution for another unknown. Many of us tried this technique in high school algebra, only to find it requires too much calculation by hand to be practical for more than three variables. In fact, the required number of arithmetic calculations goes up as the cube of the number of equations.
Because the required number of arithmetic operations to solve a set of more than a handful of linear equations grows so rapidly with the number of equations, lacking computers, much of the work in linear algebra until the mid-20th century focused on mathematical properties of A such as: Can we determine if a given set of equations has a unique solution? How can we find the inverse of A, a matrix B such that BA = I so that we can find a solution for different values of b with limited extra work? How can we get a good approximate solution when we have too few or too many measurements? Because A describes the structure of a system, can we find properties of A, its eigenvalues, that characterize the system such as the frequencies of vibration in a mechanical system?
The early 1970s was an auspicious time for numerical linear algebra. Computers that could tackle large numerical problems became available to the technical and research communities at sites such as the national laboratories. The high-level programming language FORTRAN replaced the necessity to program in machine code, thus allowing programmers to create applications whose code was closer to mathematical notation and independent of any particular computer. These advances enabled members of the technical community to write programs for their applications. Such programs could be very large and require a long time to develop. There were problems with limited memory and numerical accuracy. At the same time, researchers and practitioners in other fields were seeing the possibilities of solving their problems with computers.
At Argonne National Laboratory, a small group of mathematicians including Cleve Moler and Jack Dongarra started work on developing two libraries of FORTRAN routines, LINPACK and EISPACK, to provide numerical solutions to problems in linear algebra.
Both these libraries were groundbreaking in multiple ways. LINPACK provided routines to solve large sets of linear equations, invert matrices and provide least squares solutions for problems when A is not square. EISPACK provided routines to find properties of matrices such as their eigenvalues. Development involved not just the implementation of mathematical algorithms but addressing problems of numerical accuracy that arise from the digital representation of numbers in the computer.
Engineers, scientists and mathematicians were quick to use these libraries (and the many extensions that followed) in their work. Cleve Moler, then a professor of mathematics at the University of New Mexico, realized that others, including his students and workers in diverse technical fields who lacked experience with linear algebra or computer programming, were unable to use these libraries because they would have to write large FORTRAN programs to access them. He created MATLAB, short for Matrix Laboratory, to provide access through a simple interface that later became the MATLAB programming language.
MATLAB provided far more, including graphics to display the results of a calculation and versions for personal computers. Over the succeeding years, MATLAB has incorporated major advances in numerical linear algebra and provided support for an ever-expanding range of application areas from statistics to biology and medicine, computer science, and the geosciences.
Return to "Celebrating Cleve Moler’s impact at UNM and beyond"
