RANK REVEALING CODE

This site contains routines for constructing rank revealing factorizations of dense matrices. The site has Matlab m files for nine algorithms that usually produce rank revealing factorizations as well as three algorithms that produce factorizations that may not reveal the rank of a matrix.

The term "rank revealing factorization" is defined and references are listed in Comparison of Rank Revealing Algorithms Applied to Matrices with Well Defined Numerical Rank .

The code should work in the environments listed below. The code was tested on computers running Windows XP with Intel processors but may also work in other environments (e.g. Vista). The code consists of Matlab m files which call compiled Fortran code created using Matlab's mex utility. Since the m files are linked to compiled code the code runs quickly and is similar in speed to built-in Matlab utilities. Many of the routines will make use of multiple cores.

For each decomposition one needs to download an appropriate Matlab m file and an associated dll file (for computers running 32 bit Matlab 7.3 or earlier), mexw32 file (for computers running 32 bit Matlab 7.4 or later) or mexw64 file (for computers running 64 bit Matlab). Note that the Student Edition of Matlab is a 32 bit version of Matlab. Matlab mex files may work only in specific versions of Matlab. The versions of Matlab where the code has been tested are listed. After downloading and unzipping the files, in Matlab move to the appropriate folder and type "test_routines" to test the code (for Matlab 7.6 or later).

Help associated with each m file describes the use of the file (for example type "help lurp" from Matlab).

Zip files with all the m files and associated dll, mexw32 or mexw64 files are at: The individual M files are: For the second group of factorizations (qrp, qrtp, lurp, lutp, and lucp) there are counterexamples where the factorizations fail to reveal rank but such counterexamples appear to be rare in practice for matrices with a well defined numerical rank in the sense that there is a large gap in the singular value spectrum at the calculated numerical rank. For the last three factorizations (lupp, lunp and qrnp) there are small (2 by 2) examples where the factorizations fail to reveal rank and, more generally, examples where the factorizations fail to reveal rank are not rare.

The above list of M files does not include routines for constructing UTV - unitary, triangular, unitary - decompositions for general unitary matrices U and V and triangular matrices T. For routines related to UTV decompositions see Apalab and UTV Tools and Expansion Pack.

Some of the above m files (qrp, svdmex, lupp, qrnp) are similar to built-in Matlab programs (qr, svd, lu, qr).

Note that the Fortran code comes from either LAPACK Version 3.0, ACM Algorithm 782, ACM Algorithm 853, modifications of LAPACK code, or new code written to LAPACK standards. For 64 bit Matlab (mexw64 files) the Fortran code was compiled using Intel Fortran 11.0 linked to the 64 bit Basic Linear Algebra Subroutines (BLAS) for Windows provided with Matlab (win64\microsoft\libmwblas.lib). For 32 bit Matlab and Matlab 7.4 or later (the mexw32 files) the Fortran code was also compiled using Intel Fortran 11.0 and was linked to the 32 bit BLAS provided with Matlab (win32\microsoft\libmwblas.lib). These BLAS libraries contain implementations of Intel MKL library, version 10.0. For 32 bit Maltab with Matlab 7.3 or earlier (the dll files) the Fortran code was compiled using Compaq Visual Fortran Version 6.0 which is linked to the BLAS in Intel's MKL library, Version 8.0.

On some computers to make sure that the programs run successfully you may need to set a variable on your computer by selecting:

Your computer should remember the setting and so you only need to set it once.

For questions or problems contact foster@math.sjsu.edu