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 .