SVDLIBC

A C Library for Computing Singular Value Decompositions

version 1.4


SVDLIBC is a C library written by Doug Rohde. It was based on the SVDPACKC library, which was written by Michael Berry, Theresa Do, Gavin O'Brien, Vijay Krishna and Sowmini Varadhan at the University of Tennessee. SVDLIBC is made available under a BSD License.

SVDLIBC offers a cleaned-up version of the code with a new library interface and a front-end executable that performs matrix file type conversions, along with computing singular value decompositions. Currently the only SVDPACKC algorithm implemented in SVDLIBC is las2, because it seems to be consistently the fastest. This algorithm has the drawback that the low order singular values may be relatively imprecise, but that is not a problem for most users who only want the higher-order values or who can tolerate some imprecision.

Installing

To install SVDLIBC:
  1. Click here to download the tar file.
  2. To unpack the tar file run this on the command-line:
    tar xvzf svdlibc.tgz
    cd SVDLIBC
  3. You may want to edit the Makefile to use your favorite compiler.
  4. Run make.
This will build the libsvd.a library, located in a directory whose name is based on your HOSTTYPE environment variable (note that some shells don't have that set properly by default). This allows compilation for different architectures on a shared file system. It will also create the command-line interface executable, called svd.

Command-line Interface

The command-line interface, svd, allows you to perform an SVD on a matrix, optionally storing the left- and right-singular vectors and the singular values in separate files. You can also use it to convert from one matrix file format to another.

Note that the SVDPACKC matrix file formats are designed to be simple and do not include magic cookies or have conventional extensions to allow the format to be determined automatically. Therefore, you may need to use the -r and -w options to specify the input and output formats.

Usage
svd [options] matrix_file
-aalgorithm Set the algorithm to use. They include:
las2Single-Vector Lanczos Method (default)
-cinfile outfile Converts a matrix file to a new format (using -r and -w to specify the old and new formats). Then exits immediately.
-ddimensions Desired number of SVD triples or dimensions (default is all)
-ebound Minimum magnitude of wanted eigenvalues for las2 (1e-30)
-kkappa Accuracy parameter for las2 (1e-6)
-iiterations Maximum algorithm settling iterations. By default it iterates as many times as necessary to obtain the desired number of dimensions, and most users will not want to adjust this. But you can set this to a lower value to speed things up, with the possible loss of some dimensions.
-ofile_root Root of files in which to store resulting U', S, and V'
-rformat Input matrix file format (see below for format specifications)
st Sparse text (default)
sth SVDPACK Harwell-Boeing text format
dt Dense text
sb Sparse binary
db Dense binary
-t Transposes the input matrix. Can be used when computing the SVD or converting the format with -c.
-vverbosity Default is 1. Use 0 for no feedback, 2 to list singular values, and 3 for the vectors too.
-wformat Output matrix file format. Options are same as for -r, but default is dense text.

If the -o option is used, the resulting U' and V' matrices will be stored in files whose name is the specified file_root with "-Ut" or "-Vt" appended to the end. The matrices stored in these files are actually the transposes of the traditionally defined U and V matrices, so that the rows of the "-Ut" matrix are the left singular vectors and the rows of the "-Vt" matrix are the right singular vectors, which is generally more convenient. The "-S" file contains an array of the singular values, the first line of which holds the number of values.

C Library Interface

The interface to the SVDLIBC library is defined in svdlib.h, which should be fairly self-explanatory.

The library defines three structures. An SMat is a pointer to a struct smat, which is a sparse matrix. A DMat is a pointer to a struct dmat, which holds a dense matrix. Finally, a SVDRec is a pointer to a struct svdrec, which holds the results of an SVD: the dimensionality (d), the left- and right- singular matrices (Ut and Vt), and file types (such as SVD_F_ST). Any file type can be loaded to or written from either a sparse or dense matrix.

Finally, the svdLAS2 function actually computes the SVD. It takes a sparse matrix and some parameters and returns an SVDRec containing the components of the SVD. svdLAS2A is a simpler version that attempts to automatically choose reasonable parameter values and requires only a matrix and the desired number of dimensions (or 0 for all).

Matrix File Formats

The sparse formats are more efficient for sparse matrices, the dense ones for dense matrices. The binary formats will be faster to read and write and will be smaller if the matrix uses high-precision floating point numbers. Values are stored in 4-byte floats, not in 8-byte doubles.

Library
Code
Command-line
Code
Description
SVD_F_ST st Sparse matrix, text format.
SVD_F_STH sth Sparse matrix, Harwell-Boeing text format used in SVDPACKC.
SVD_F_SB sb Sparse matrix, binary format.
SVD_F_DT dt Dense matrix, text format.
SVD_F_DB db Dense matrix, binary format.

Version Notes

1.4
  • Added BSD License
  • Incorporated bug fixes by piskvorky, reported here.
  • Fixed some gcc compiler warnings.
1.34
  • Worked around a gcc optimizer bug that was reordering statements in the initial precision calculations, resulting in bad computations on some Linux machines.
  • Fixed some g++ compiler warnings.
  • Fixed the icc compiler flags for Linux machines.
1.33
  • Fixed a numeric overflow problem in the matrix validation which caused errors for high-dimensional matrices.
1.32
  • Upgraded the Harwell-Boeing input and output file formats to better support the spec. Files output in this format by version 1.32 or later may not be readable by earlier versions of the library.
1.31
  • Fixed type errors that caused problems on AIX systems.
1.3
  • Removed the need to specify the number of iterations. It should now use less memory and always get the correct answer if the number of iterations is not given.
  • Removed a bug that prevented obtaining just 1 or 2 dimensions.
  • The -t option was added to allow matrix transposition, which is done efficiently for sparse matrices.
  • Matrices with significantly more columns than rows will be transformed before the SVD is computed to improve the speed.
1.21
  • Fixed a bug that caused segmentation faults when the number of iterations was as large as the matrix size.
1.2
  • The memory usage has been reduced, allowing svdLAS2() to handle larger matrices.
1.1
  • The svdLAS2A() function has been added.
  • The second and third arguments to svdLAS2() have been swapped so dimensions comes before iterations.
  • Renamed internal functions to prevent linker conflicts with the DRUtils library.
1.01
  • Fixed a bug (which exists in SVDPACKC) that produced incorrect results in matrices with less than full rank. Thanks to Greg Landrum for pointing out this problem.
1.0
  • The first one.

Feedback

Comments, questions, and bug reports should be addressed to
dr+svd@tedlab.mit.edu.


Doug Rohde, dr+svd@tedlab.mit.edu,
Department of Brain and Cognitive Science,
Massachusetts Institute of Technology