[CONTACT]

[ABOUT]

[POLICY]

[ADVERTISE]

SPARSE SVD VIA HYBRID BLOCK

Found at: ftp.icm.edu.pl:70/packages/netlib/svdpack/bld1

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

		
.


AD:

NEW PAGES:

[ODDNUGGET]

[GOPHER]