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 code was updated on 6-19-2012 with the addition of the Linux routines.
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 .
code should work in the environments listed below. The code was tested on
computers running Windows XP, Windows 7 and Linux
with Intel processors but may also work in other environments (e.g. AMD processors).
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 Windows computers running 32 bit Matlab 7.3 or
earlier), mexw32 file (for Windows computers running 32 bit Matlab 7.4 or later), mexw64 file
(for Windows computers running 64 bit Matlab 7.6 or later), or mexa64 (for Linux computers running
64 bit Matlab with an Intel x86-64 or compatible processor). 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.
- Rank revealing factorizations:
- svdmex.m -- the singular value decomposition (LAPACK's DGESDD)
- qrxp.m -- QR factorization using the routine DGEQPX from ACM Algorithm 782
- qryp.m -- QR factorization using the routine DGEQPY from ACM Algorithm 782
- lupan3.m -- LU factorization based on a modification of an algorithm due to C. T. Pan
- Factorizations that are usually rank revealing but have a possibility of failure:
- qrp.m -- QR factorization with column interchanges using LAPACK's routine DGEQP3.
- qrtp.m -- Partial QR factorization using the routine DLAQP3 from ACM Algorithm 853.
- lurp.m -- LU factorization using Gaussian elimination with rook pivoting
- lutp.m -- LU factorizations using Gaussian elimination with threshold rook pivoting
- lucp.m -- LU factorization using Gaussian elimination with complete pivoting
- Factorizations that often do not reveal rank correctly:
- lupp.m -- LU factorization using Gaussian elimination with partial pivoting (LAPACK's DGETRF)
- lunp.m -- LU factorization using Gaussian elimination with no pivoting (modification of DGETRF)
- qrnp.m -- QR factorization with no column interchanges using LAPACK's routine DGEQRF.
- Testing routines:
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).
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 with Linux (mexa64 files), the Fortran code was compiled with gfortran 4.3.6
linked to the 64 bit Basic Linear Algebra Subroutines (BLAS)
provided with Matlab.
For 64 bit Matlab with Windows (mexw64 files),the Fortran code was compiled
using Intel Fortran 11.0 linked to the 64 bit BLAS
provided with Matlab (win64\microsoft\libmwblas.lib).
For 32 bit Matlab and Matlab 7.4 or later (the mexw32 files) the Fortran code was
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 older 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
- control panel
- environmental variables
- new (from user variables)
- and the typing for the variable name:
- and typing for the variable value:
- then click on ok