Line data    Source code

       1             : /*
       2             :    - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
       3             :    SLEPc - Scalable Library for Eigenvalue Problem Computations
       4             :    Copyright (c) 2002-, Universitat Politecnica de Valencia, Spain
       5             : 
       6             :    This file is part of SLEPc.
       7             :    SLEPc is distributed under a 2-clause BSD license (see LICENSE).
       8             :    - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
       9             : */
      10             : /*
      11             :    SLEPc singular value solver: "randomized"
      12             : 
      13             :    Method: RSVD
      14             : 
      15             :    Algorithm:
      16             : 
      17             :        Randomized singular value decomposition.
      18             : 
      19             :    References:
      20             : 
      21             :        [1] N. Halko, P.-G. Martinsson, and J. A. Tropp, "Finding
      22             :            structure with randomness: Probabilistic algorithms for
      23             :            constructing approximate matrix decompositions", SIAM Rev.,
      24             :            53(2):217-288, 2011.
      25             : */
      26             : 
      27             : #include <slepc/private/svdimpl.h>                /*I "slepcsvd.h" I*/
      28             : 
      29          11 : static PetscErrorCode SVDSetUp_Randomized(SVD svd)
      30             : {
      31          11 :   PetscInt       N;
      32             : 
      33          11 :   PetscFunctionBegin;
      34          11 :   SVDCheckStandard(svd);
      35          11 :   SVDCheckDefinite(svd);
      36          11 :   SVDCheckUnsupported(svd,SVD_FEATURE_THRESHOLD);
      37          11 :   PetscCheck(svd->which==SVD_LARGEST,PetscObjectComm((PetscObject)svd),PETSC_ERR_SUP,"This solver supports only largest singular values");
      38          11 :   PetscCall(MatGetSize(svd->A,NULL,&N));
      39          11 :   PetscCall(SVDSetDimensions_Default(svd));
      40          11 :   PetscCheck(svd->ncv>=svd->nsv,PetscObjectComm((PetscObject)svd),PETSC_ERR_USER_INPUT,"The value of ncv must not be smaller than nsv");
      41          11 :   if (svd->max_it==PETSC_DETERMINE) svd->max_it = PetscMax(N/svd->ncv,100);
      42          11 :   svd->leftbasis = PETSC_TRUE;
      43          11 :   svd->mpd = svd->ncv;
      44          11 :   PetscCall(SVDAllocateSolution(svd,0));
      45          11 :   PetscCall(DSSetType(svd->ds,DSSVD));
      46          11 :   PetscCall(DSAllocate(svd->ds,svd->ncv));
      47          11 :   PetscCall(SVDSetWorkVecs(svd,1,1));
      48          11 :   PetscFunctionReturn(PETSC_SUCCESS);
      49             : }
      50             : 
      51         383 : static PetscErrorCode SVDRandomizedResidualNorm(SVD svd,PetscInt i,PetscScalar sigma,PetscReal *res)
      52             : {
      53         383 :   PetscReal      norm1,norm2;
      54         383 :   Vec            u,v,wu,wv;
      55             : 
      56         383 :   PetscFunctionBegin;
      57         383 :   *res = 1.0;
      58         383 :   if (svd->conv!=SVD_CONV_MAXIT) {
      59         381 :     wu = svd->swapped? svd->workr[0]: svd->workl[0];
      60         381 :     wv = svd->swapped? svd->workl[0]: svd->workr[0];
      61         381 :     PetscCall(BVGetColumn(svd->V,i,&v));
      62         381 :     PetscCall(BVGetColumn(svd->U,i,&u));
      63             :     /* norm1 = ||A*v-sigma*u||_2 */
      64         381 :     PetscCall(MatMult(svd->A,v,wu));
      65         381 :     PetscCall(VecAXPY(wu,-sigma,u));
      66         381 :     PetscCall(VecNorm(wu,NORM_2,&norm1));
      67             :     /* norm2 = ||A^T*u-sigma*v||_2 */
      68         381 :     PetscCall(MatMult(svd->AT,u,wv));
      69         381 :     PetscCall(VecAXPY(wv,-sigma,v));
      70         381 :     PetscCall(VecNorm(wv,NORM_2,&norm2));
      71         381 :     PetscCall(BVRestoreColumn(svd->V,i,&v));
      72         381 :     PetscCall(BVRestoreColumn(svd->U,i,&u));
      73         381 :     *res = SlepcAbs(norm1,norm2);
      74             :   }
      75         383 :   PetscFunctionReturn(PETSC_SUCCESS);
      76             : }
      77             : 
      78             : /* If A is a virtual Hermitian transpose, then BVMatMult will fail if PRODUCT_AhB is not implemented */
      79         688 : static PetscErrorCode BlockMatMult(BV V,Mat A,BV Y,Mat AT)
      80             : {
      81         688 :   PetscFunctionBegin;
      82         688 :   if (!PetscDefined(USE_COMPLEX)) PetscCall(BVMatMult(V,A,Y));
      83             :   else {
      84             :     PetscBool flg=PETSC_FALSE;
      85             :     PetscCall(PetscObjectTypeCompare((PetscObject)A,MATHERMITIANTRANSPOSEVIRTUAL,&flg));
      86             :     if (flg) PetscCall(BVMatMultHermitianTranspose(V,AT,Y));
      87             :     else PetscCall(BVMatMult(V,A,Y));
      88             :   }
      89         688 :   PetscFunctionReturn(PETSC_SUCCESS);
      90             : }
      91             : 
      92          11 : static PetscErrorCode SVDSolve_Randomized(SVD svd)
      93             : {
      94          11 :   PetscScalar    *w;
      95          11 :   PetscReal      res=1.0;
      96          11 :   PetscInt       i,k=0;
      97          11 :   Mat            A,U,V;
      98             : 
      99          11 :   PetscFunctionBegin;
     100             :   /* Form random matrix, G. Complete the initial basis with random vectors */
     101          11 :   PetscCall(BVSetActiveColumns(svd->V,svd->nini,svd->ncv));
     102          11 :   PetscCall(BVSetRandomNormal(svd->V));
     103          11 :   PetscCall(PetscCalloc1(svd->ncv,&w));
     104             : 
     105             :   /* Subspace Iteration */
     106         344 :   do {
     107         344 :     svd->its++;
     108         344 :     PetscCall(BVSetActiveColumns(svd->V,svd->nconv,svd->ncv));
     109         344 :     PetscCall(BVSetActiveColumns(svd->U,svd->nconv,svd->ncv));
     110             :     /* Form AG */
     111         344 :     PetscCall(BlockMatMult(svd->V,svd->A,svd->U,svd->AT));
     112             :     /* Orthogonalization Q=qr(AG)*/
     113         344 :     PetscCall(BVOrthogonalize(svd->U,NULL));
     114             :     /* Form B^*= AQ */
     115         344 :     PetscCall(BlockMatMult(svd->U,svd->AT,svd->V,svd->A));
     116             : 
     117         344 :     PetscCall(DSSetDimensions(svd->ds,svd->ncv,svd->nconv,svd->ncv));
     118         344 :     PetscCall(DSSVDSetDimensions(svd->ds,svd->ncv));
     119         344 :     PetscCall(DSGetMat(svd->ds,DS_MAT_A,&A));
     120         344 :     PetscCall(MatZeroEntries(A));
     121         344 :     PetscCall(BVOrthogonalize(svd->V,A));
     122         344 :     PetscCall(DSRestoreMat(svd->ds,DS_MAT_A,&A));
     123         344 :     PetscCall(DSSetState(svd->ds,DS_STATE_RAW));
     124         344 :     PetscCall(DSSolve(svd->ds,w,NULL));
     125         344 :     PetscCall(DSSort(svd->ds,w,NULL,NULL,NULL,NULL));
     126         344 :     PetscCall(DSSynchronize(svd->ds,w,NULL));
     127         344 :     PetscCall(DSGetMat(svd->ds,DS_MAT_U,&U));
     128         344 :     PetscCall(DSGetMat(svd->ds,DS_MAT_V,&V));
     129         344 :     PetscCall(BVMultInPlace(svd->U,V,svd->nconv,svd->ncv));
     130         344 :     PetscCall(BVMultInPlace(svd->V,U,svd->nconv,svd->ncv));
     131         344 :     PetscCall(DSRestoreMat(svd->ds,DS_MAT_U,&U));
     132         344 :     PetscCall(DSRestoreMat(svd->ds,DS_MAT_V,&V));
     133             :     /* Check convergence */
     134         344 :     k = 0;
     135         384 :     for (i=svd->nconv;i<svd->ncv;i++) {
     136         383 :       PetscCall(SVDRandomizedResidualNorm(svd,i,w[i],&res));
     137         383 :       svd->sigma[i] = PetscRealPart(w[i]);
     138         383 :       PetscCall((*svd->converged)(svd,svd->sigma[i],res,&svd->errest[i],svd->convergedctx));
     139         383 :       if (svd->errest[i] < svd->tol) k++;
     140             :       else break;
     141             :     }
     142         344 :     if (svd->conv == SVD_CONV_MAXIT && svd->its >= svd->max_it) {
     143           2 :       k = svd->nsv;
     144          22 :       for (i=0;i<svd->ncv;i++) svd->sigma[i] = PetscRealPart(w[i]);
     145             :     }
     146         344 :     PetscCall((*svd->stopping)(svd,svd->its,svd->max_it,svd->nconv+k,svd->nsv,&svd->reason,svd->stoppingctx));
     147         344 :     svd->nconv += k;
     148         344 :     PetscCall(SVDMonitor(svd,svd->its,svd->nconv,svd->sigma,svd->errest,svd->ncv));
     149         344 :   } while (svd->reason == SVD_CONVERGED_ITERATING);
     150          11 :   PetscCall(PetscFree(w));
     151          11 :   PetscFunctionReturn(PETSC_SUCCESS);
     152             : }
     153             : 
     154           9 : SLEPC_EXTERN PetscErrorCode SVDCreate_Randomized(SVD svd)
     155             : {
     156           9 :   PetscFunctionBegin;
     157           9 :   svd->ops->setup          = SVDSetUp_Randomized;
     158           9 :   svd->ops->solve          = SVDSolve_Randomized;
     159           9 :   PetscFunctionReturn(PETSC_SUCCESS);
     160             : }