Eigenvalues Calculator of a Real Symmetric Matrix

This program computes the eigenvalues of a real symmetric matrix. The program accepts input of a full matrix, A, tests it for symmetry and, if symmetry is confirmed, calculates its eigenvalues. A limit on the size of A is not imposed by the routine. The underlying algorithm is designed to handle real symmetric matrices of any size; however, as the system grows, getting the input data into the DOM textarea on the web page might cause it to hiccup. (Anybody wishing to keep entering larger and larger systems until it breaks, feel free to test it!) The only restriction on A is that its coefficients be real; this program was not written to handle complex coefficients.

The routine is a heavily-edited translation of the EISPACK subprogram RS.F.

References:

Smith, B.T.; J.M. Boyle; J.J. Dongarra; B.S. Garbow; Y. Ikebe; V.C. Klema; and C.B. Moler.
      "Matrix Eigensystem Routines--(EISPACK) Guide"
      Springer-Verlag, Berlin.
      1976

Garbow, B.S.; J.M. Boyle; J.J. Dongarra; and C.B. Moler.
      "Matrix Eigensystem Routines--(EISPACK) Guide Extension"
      Springer-Verlag, Berlin.
      1977

I would like to emphasize that only eigenvalues are computed; eigenvectors are not. In fact, because only eigenvalues are calculated, only two sub-routines from RS.F were needed: TRED1 and TQL1. The sub-routines for computing both the eigenvalues and eigenvectors (i.e., TRED2 and TQL2) were not needed, so not translated.

TRED1 reduces a real symmetric matrix to a symmetric tridiagonal matrix using orthogonal similarity transformations. It is a translation of the algol procedure tred1, Num. Math. 11, 181-195 (1968) by Martin, Reinsch, and Wilkinson. Handbook for Auto. Comp., vol.ii-linear algebra, 212-226 (1971).

TQL1 finds the eigenvalues of a symmetric tridiagonal matrix by the ql method. It is a translation of the algol procedure tql1, Num. Math. 11, 293-306 (1968) by Bowdler, Martin, Reinsch, and Wilkinson. Handbook for Auto. Comp., vol.ii-linear algebra, 227-240 (1971).

This program is not a straight sub-routine to sub-routine translation: TRED1 and TQL1 are both coded into a single sub-routine and their positions within the program are indicated by comments.

A C++ translation of this program is available on GitHub.
It includes a small sub-routine (Echo2DArray, lines 280 - 291) for outputting the input array, A, to the console. Its call in the main program has been commented out. Anybody wishing to use this program, and to make it smaller, can delete this routine completely.

Note that the main program accepts input of a full symmetric matrix and tests it for symmetry before passing the matrix into the sub-routine that calculates its eigenvalues. Two comments about this aspect of the program:

1) Instead of testing that coefficients across the diagonal are equal, the absolute value of their difference is tested against DBL_EPSILON
(i.e., if (fabs(A[i][j] - A[j][i]) > DBL_EPSILON)).
Testing for true equality (i.e., if (a == b)) when dealing with floating point numbers can lead to unexpected results.

2) The symmetry test is intended to be one more way in which to catch errors: prompting the user to review the data may reveal a typo in a data entry, for instance. The sub-routine that calculates the eigenvalues, in fact, only touches the lower triangular half of the A matrix (coefficients along and below the diagonal.) Coefficients above the diagonal are not touched by the sub-routine.

One final comment before concluding this post. The routine changes the input matrix, A. So, if this routine is incorporated into a larger program, and the original version of A is needed later, be sure to make a copy of A, and then pass the copy into the routine.

Eigenvalue and Eigenvector Calculator

The web page to which the title of this post is hot linked is the most recent utility I have added for computing the eigenvalues and eigenvectors of a real general matrix. It accepts square matrices of up to size twelve by twelve (this limit was arbitrarily picked by me, because that was the largest size matrices with which I worked during my undergraduate engineering studies).

As cited on the page itself, this eigenvalue and eigenvector solver is a translation of routines that come from the EISPACK collection of routines, specifically, balanc, hqr2, elmhes, eltran, and balbak.

Note that the results of the computation may be complex, but the inputs are all assumed to be real entries.

Also note that this utility can solve symmetric matrices, but using a program specifically written for symmetric matrices would be more efficient.

Free Math Tools for Science and Engineering Students

On the page in the title of this post are presented links to several numerical mathematics tools, programs written in Javascript for performing specific numerical tasks. I have been working on these math programs for several years but never explained why I do it. So, here goes . . .

When I was an engineering undergraduate, commercial mathematics software was not provided by my school. When the need arose for computer programs that solved math problems, we either searched for existing code or wrote the programs ourselves. At the time, I found good-quality source code written in FORTRAN but had a “C” compiler. So I translated the programs from FORTRAN into “C”. Then, instead of letting the programs sit on a floppy disk in the closet doing nothing, I translated them from “C” into Javascript. (In fact, I have received several requests for “C” source code, so that is slowly getting posted too.)

Posting the routines online as Javascript programs transforms them from passive documents into dynamic, immediate-for-use, tools accessible to anybody with an Internet connection. A few other aspects of Javascript are worth mentioning:

1) Javascript syntax is very similar to that of “C”, so the translation from “C” to Javascript is pretty simple.
2) Javascript programs incorporated in a web page can be run in any browser, regardless of whether the page is being viewed on a computer running Windows, Linux, Mac, etc.
3) A separate executable does not have to be downloaded nor does a plug-in have to be installed.
4) The pages can be saved and the programs can be used in a browser offline.

Over the years, the number of routines posted on the site has grown significantly: there are now utilities for computing the roots of polynomial equations, solving simultaneous equations, computing eigenvalues and eigenvectors, linear least-square data-fitting, cubic spline interpolation, minimization/maximization, numerical integration, and more. In addition, more are planned.

Finally, one short note before I conclude this post. The interface for many of the utilities is getting changed slightly. Instead of requiring all the inputs to be typed in individually, which can get quite tedious and increases the chances of entering typos, more use is being made of textarea boxes, in which all input data can be entered at once. This approach gives users the capability to copy data from a plain-text document and then pasted into the form--a much quicker process and one that eliminates the potential for typos in the input data. In other words, regardless of where the data may come from, as long as it is first copied into a plain-text document and arranged in the appropriate format, it can then quickly and easily be copied into the data input box of the utility.