Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
1. OVERVIEW OF THE PACKAGE Below is a list giving a brief description of the files found in the package. ============================================================================ Readme : This description. Main routines ------------- lanbpro.m : Lanczos bidiagonalization with partial reorthogonalization (BPRO). lansvd.m : Sparse SVD routine built on BPRO. lanpro.m : Lanczos tridiagonalization with partial reorthogonalization (PRO). laneig.m : Sparse symmetric eigenvalue routine built on PRO. Similar to the "lanso" subroutine in the LANSO package. Computational routines ---------------------- refinebounds.m: Refines the error bounds based on the gap structure of the Ritz values. compute_int.m : Routine for determining which Lanczos vectors to purge in a reorthogonalization. reorth.m : Iterated (modified or classical) Gram-Schmidt reorthogonalization. reorth.mex<...> : MEX file using a FORTRAN 77 version of reorth.m. tqlb.m : Computes the eigenvalues and the top and bottom elements of the eigenvectors for a symmetric tridiagonal matrix. tqlb.mex<...> : The corresponding MEX files call a modified version of the EISPACK routine TQL1 (see below). bdsqr.m : Computes the singular values and the bottom elements of the left singular vectors for a lower bidiagonal matrix. bdsqr.mex<...>: The corresponding MEX files call the LAPACK routine DBDSQR. Test scripts and test problems ------------------------------ test.m : Main script for testing sparse SVD calculations. testtqlb.m : Script for comparing different versions of TQLB. Afunc.m : Function that computes Y <- A*X. Atfunc.m : Function that computes Y <- A'*X. AtAfunc.m : Function that computes Y <- A'*A*X. Cfunc.m : Function that computes Y <- [A*X(m+1:m+n,:); A'*X(1:m,:)] i.e. Y = [ 0 A ] * X [ A' 0 ]. helio.mat : Testproblem from helioseismology. It is a full 212 x 100 matrix with condition number 2.9*10^12. Harwell-Boeing/ : Directory with various testmatrices from the Harwell-Boeing collection (in Matrix Market format). The directory also contains Matlab function for querying, reading and writing matrices stored in Matrix Market file format. ============================================================================ The routine TQLB is used for computing the eigenvalues and top and bottom elements of the eigenvectors of the Lanczos tridiagonal, which enter into the error bounds. TQLB is based on an optimized version of the EISPACK routine TQL1 (see below), and for the sake of speed FORTRAN versions of TQLB, the reorthogonalization routine REORTH and the LAPACK routine DBDSQR have been included as MEX files. The current versions of the MEX files have been compiled for SGI64, SUN and Linux x86 machines. Purely Matlab based versions are included for use on other platforms, but these can be rather slow in comparison. 2. IMPLEMENTATION DETAILS 2.1 Modifications to tqlb relative to the version used in the lanso package: In TQLB I have added a little extra code to compute the bottom elements of the normalized eigenvectors. In addition I have replaced the calls to PYTHAG in the inner loop of the QL iteration with in-line code according to the suggestions in A. Cline and J. Meyering, "Converting EISPACK to run efficiently on a vector processor", Tech. Memo., Pleasant Valley Software, Austin TX, 1989. (see their code in http://www.netlib.org/eispack/3090vf/double/tql1.f). Apart from decreasing the execution time by a factor of 3 compared to the original version, it also causes the small eigenvalues to be computed more accurately. As a test I computed the eigenvalues of the standard testmatrix: ( 2 -1 ) ( -1 2 -1 ) T = ( -1 2 . ) , ( . . -1 ) ( -1 2 ) where the true eigenvalues are lambda_i = 4 * cos(pi/2 * i / n+1)^2, i = 1,2,...,n . Below are the results (T=time in seconds, E=max relative error) obtained on an SGI Origin 200 with a 180MHz MIPS R10000 CPU, 32Kbytes primary, 1Mb secondary cache: Original TQLB Modified TQLB MATLAB EIG (eigenvalues only) ----------------------------------------------------------------------------- n T E T E T E 100 0.020 1.4e-12 0.007 3.1e-13 0.024 6.2e-14 1000 1.68 1.2e-9 0.55 2.9e-10 1.98 1.5e-10 10000 154.1 1.9e-6 52.2 8.2e-8 181.2 3.0e-8 ============================================================================== Rasmus Munk Larsen, Stanford University, 2000