BLSVD-1: SPARSE SVD VIA HYBRID BLOCK LANCZOS PROCEDURE (VER. 1.0) FOR
EQUIVALENT 2-CYCLIC EIGENSYSTEMS
BLSVD IS A PROGRAM WRITTEN IN FORTRAN 77 DESIGNED TO COMPUTE
SINGULAR VALUES AND SINGULAR VECTORS OF A LARGE SPARSE MATRIX A.
THIS IS A MODIFIED VERSION OF THE BLOCK LANCZOS ALGORITHM FIRST
PUBLISHED BY GOLUB, LUK, AND OVERTON (ACM TOMS 7(2):149-169, 1981).
THIS PARTICULAR IMPLEMENTATION IS DISCUSSED IN "MULTIPROCESSOR
SPARSE SVD ALGORITHMS AND APPLICATIONS", PH.D. THESIS BY M. BERRY,
UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN, OCTOBER 1990.
THIS "HYBRID" BLOCK LANCZOS PROCEDURE CONSISTS OF FIVE PHASES:
PHASE 1: BLOCK LANCZOS OUTER ITERATION TO YIELD A BLOCK UPPER
BIDIAGONAL MATRIX B WHICH SHARES THE SAME SINGULAR
VALUES OF THE ORIGINAL SPARSE MATRIX A. TOTAL OR
COMPLETE RE-ORTHOGONALIZATION IS USED HERE.
PHASE 2: LANCZOS METHOD FOR BI-DIAGONALIZING THE S MATRIX FROM
PHASE 1 TO YIELD THE BI-DIAGONAL MATRIX B WHICH PRESERVES
THE SAME SINGULAR VALUES. COMPLETE OR TOTAL RE-ORTHOGONAL-
IZATION IS USED FOR THIS LANCZOS RECURSION. A POINT
LANCZOS METHOD IS USED IF A BLOCKSIZE (NB) OF 1 IS ENCOUNTERED.
PHASE 3: APPLY AN APPROPRIATE QR ITERATION TO DIAGONALIZE B AND
HENCE PRODUCE APPROXIMATE SINGULAR VALUES (ARRAY ALPHA)
OF THE ORIGINAL MATRIX A.
PHASE 4: CONVERGENCE TEST USING A USER-SUPPLIED RESIDUAL TOLERANCE
(TOL)
PHASE 5: ITERATION RESTART WITH ORTHOGONAL PROJECTION WITH RESPECT
TO ANY (ALL) CONVERGED SINGULAR VECTORS.
- HOW TO USE SUBROUTINE BLKLAN FOR THE SVD (CALLED BY MAIN PROGRAM)
THE CALLING SEQUENCE FOR BLKLAN IS
.
CALL BLKLAN(M,N,IK,LDV,V,LDU,U,SING,IC,IB,ITER,TOL,RES,MAXIT,
IK0,IC0,IB0,IMEM)
.
THE USER SPECIFIES AS PART OF THE PARAMETER LIST:
.
M ... ROW DIMENSION OF THE SPARSE MATRIX A WHOSE SVD
IS SOUGHT {INTEGER}.
N ... COLUMN DIMENSION OF THE SPARSE MATRIX A WHOSE SVD
IS SOUGHT {INTEGER}.
IK ... NUMBER OF SINGULAR TRIPLETS (SINGULAR VALUES AND
THEIR CORRESPONDING SINGULAR VECTORS) DESIRED
{INTEGER}.
IB ... INITIAL BLOCK SIZE FOR OUTER ITERATION {INTEGER}.
IC ... UPPER BOUND FOR DIMENSION OF KRYLOV SUBSPACE
GENERATED VIA OUTER ITERATION {INTEGER}. IC IS THE
MAXIMUM DIMENSION FOR THE BLOCK UPPER BIDIAGONAL
MATRIX S GENERATED IN PHASE 1 ABOVE.
LDV ... LEADING DIMENSION OF ARRAY V WHICH CONTAINS
APPROXIMATE RIGHT SINGULAR VECTORS ON OUTPUT
{INTEGER}. LDV MUST BE GREATER THAN OR EQUAL
TO N.
LDU ... LEADING DIMENSION OF ARRAY U WHICH CONTAINS
APPROXIMATE LEFT SINGULAR VECTORS ON OUTPUT
{INTEGER}. LDU MUST BE GREATER THAN OR EQUAL TO M.
TOL ... USER-SPECIFIED TOLERANCE FOR APPROXIMATE SINGULAR
TRIPLETS {REAL*8}.
MAXIT ... MAXIMUM NUMBER OF OUTER ITERATIONS ALLOWED
{INTEGER}.
.
BLKLAN RETURNS VIA ITS PARAMETER LIST THE FOLLOWING ITEMS:
.
ITER ... NUMBER OF OUTER ITERATIONS REQUIRED {INTEGER}.
IMEM ... ESTIMATE OF STORAGE NEEDED (IN BYTES) {INTEGER}.
IB0 ... FINAL BLOCK SIZE USED IN OUTER ITERATION {INTEGER}.
IC0 ... LAST BOUND FOR DIMENSION OF KRYLOV SUBSPACE
USED WITHIN OUTER ITERATION {INTEGER}.
IK0 ... NUMBER OF SINGULAR TRIPLETS APPROXIMATED {INTEGER}.
SING ... ONE-DIMENSIONAL ARRAY CONTAINING THE IK0
APPROXIMATE SINGULAR VALUES {REAL*8}.
V ... TWO-DIMENSIONAL ARRAY CONTAINING THE IK0
APPROXIMATE RIGHT SINGULAR VECTORS CORRESPONDING
TO THE APPROXIMATE SINGULAR VALUES IN ARRAY
SING {REAL*8}.
U ... TWO-DIMENSIONAL ARRAY CONTAINING THE IK0
APPROXIMATE LEFT SINGULAR VECTORS CORRESPONDING
TO THE APPROXIMATE SINGULAR VALUES IN ARRAY
SING {REAL*8}.
RES ... ONE-DIMENSIONAL ARRAY CONTAINING THE IK0
RESIDUALS OF THE APPROXIMATE SINGULAR TRIPLETS
{REAL*8}.
.
SPARSE MATRIX-VECTOR MULTIPLICATION SUBROUTINES OP AND OPT
MUST BE SUPPLIED BY THE USER.
.
THE CALLING SEQUENCE FOR OP IS
.
CALL OP(M,N,X,Y)
.
OP TAKES AN N-VECTOR X AND RETURNS THE M-VECTOR Y = A*X.
IN OUR TEST PROGRAM, BLS1, WE EMPLOY THE HARWELL-BOEING SPARSE MATRIX
FORMAT FOR ACCESSING ELEMENTS OF THE M BY N SPARSE MATRIX A AND ITS
TRANSPOSE. OTHER SPARSE MATRIX FORMATS CAN BE USED, OF COURSE.
.
THE CALLING SEQUENCE FOR OPT IS
.
CALL OPT(N,M,X,Y)
OPT TAKES AN M-VECTOR X AND RETURNS THE N-VECTOR Y = A'*X, WHERE
A' DENOTES THE TRANSPOSE OF THE MATRIX A.
.
IN ADDITION, BLKLAN REQUIRES THE FOLLOWING USER-SUPPLIED PARAMETERS
FOR TEMPORARY ARRAY ALLOCATIONS.
.
USER-SUPPLIED PARAMETERS FOR BLKLAN:
.
USER SHOULD SET IB2 = INITIAL BLOCK SIZE (IB)
IK2 = NUMBER OF DESIRED SINGULAR VALUES (IK)
IC2 = INITIAL KRYLOV SUBSPACE DIMENSION (IC)
M2 = ROW DIMENSION OF SPARSE MATRIX A ( M)
N2 = COL DIMENSION OF SPARSE MATRIX A ( N)
LDT2 = MAX(M2,N2)
.
SAMPLE DECLARATION FROM BLS1 FILE FOR LAI7 DATASET:
.
PARAMETER(IB2=10, IK2=10, IC2=50, M2=374, N2=82, LDT2=374)
.
THIS VERSION OF BLKLAN IS DESIGNED TO APPROXIMATE THE IK-LARGEST
SINGULAR TRIPLETS OF A. USERS INTERESTED IN THE IK-SMALLEST
SINGULAR TRIPLETS NEED ONLY SORT THE ALPHA ARRAY IN INCREASING
(AS OPPOSED TO THE DEFAULT ASCENDING ORDER) FOLLOWING THE LINE
CALL QRITER2(NN,NN,ALPHA,BETA,QQ,IC2,PP,IC2,INFO)
WITHIN THE BLS1 SOURCE. THE COLUMNS OF THE TWO-DIMENSIONAL ARRAYS
PP AND QQ MUST BE REORDERED TO REFLECT A ONE-TO-ONE CORRESPONDENCE
WITH THE NEWLY SORTED ELEMENTS OF ALPHA (WHICH ARE APPROXIMATE
SINGULAR VALUES OF THE MATRIX A).
.
EXPLICIT CALLS TO THE UNIX TIMER "ETIME" IS MADE IN THE BLS1 SOURCE.
A CALL TO ANOTHER TIMING ROUTINE (ELAPSED CPU TIME) MADE BE NEEDED.
.
IF THE PARAMETER "VECTORS" (READ FROM BLI5) IS SET TO "TRUE",
THE UNFORMATTED OUTPUT FILE BLO8 WILL CONTAIN THE APPROXIMATE
SINGULAR VECTORS WRITTEN IN THE ORDER U[1], V[1], U[2], V[2],
..., U[IK0], V[IK0]. HERE U[I] AND V[I] DENOTE THE LEFT AND RIGHT
SINGULAR VECTORS, RESPECTIVELY, CORRESPONDING TO THE I-TH
APPROXIMATE SINGULAR VALUE, SING[I].
- INFORMATION
PLEASE ADDRESS ALL QUESTIONS, COMMENTS, OR CORRECTIONS TO:
M. W. BERRY
DEPARMENT OF COMPUTER SCIENCE
UNIVERSITY OF TENNESSEE
107 AYRES HALL
KNOXVILLE, TN 37996-1301
EMAIL: BERRY@CS.UTK.EDU
PHONE: (615) 974-5067
.