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 eigensolver: "arnoldi"
      12             : 
      13             :    Method: Explicitly Restarted Arnoldi
      14             : 
      15             :    Algorithm:
      16             : 
      17             :        Arnoldi method with explicit restart and deflation.
      18             : 
      19             :    References:
      20             : 
      21             :        [1] "Arnoldi Methods in SLEPc", SLEPc Technical Report STR-4,
      22             :            available at https://slepc.upv.es.
      23             : */
      24             : 
      25             : #include <slepc/private/epsimpl.h>                /*I "slepceps.h" I*/
      26             : 
      27             : typedef struct {
      28             :   PetscBool delayed;
      29             : } EPS_ARNOLDI;
      30             : 
      31          29 : static PetscErrorCode EPSSetUp_Arnoldi(EPS eps)
      32             : {
      33          29 :   PetscFunctionBegin;
      34          29 :   EPSCheckDefinite(eps);
      35          29 :   EPSCheckNotStructured(eps);
      36          29 :   PetscCall(EPSSetDimensions_Default(eps,eps->nev,&eps->ncv,&eps->mpd));
      37          29 :   PetscCheck(eps->ncv<=eps->nev+eps->mpd,PetscObjectComm((PetscObject)eps),PETSC_ERR_USER_INPUT,"The value of ncv must not be larger than nev+mpd");
      38          29 :   if (eps->max_it==PETSC_DETERMINE) eps->max_it = PetscMax(100,2*eps->n/eps->ncv);
      39          29 :   if (!eps->which) PetscCall(EPSSetWhichEigenpairs_Default(eps));
      40          29 :   PetscCheck(eps->which!=EPS_ALL,PetscObjectComm((PetscObject)eps),PETSC_ERR_SUP,"This solver does not support computing all eigenvalues");
      41          29 :   EPSCheckUnsupported(eps,EPS_FEATURE_ARBITRARY | EPS_FEATURE_TWOSIDED);
      42             : 
      43          29 :   PetscCall(EPSAllocateSolution(eps,1));
      44          29 :   PetscCall(EPS_SetInnerProduct(eps));
      45          29 :   PetscCall(DSSetType(eps->ds,DSNHEP));
      46          29 :   if (eps->extraction==EPS_REFINED || eps->extraction==EPS_REFINED_HARMONIC) PetscCall(DSSetRefined(eps->ds,PETSC_TRUE));
      47          29 :   PetscCall(DSSetExtraRow(eps->ds,PETSC_TRUE));
      48          29 :   PetscCall(DSAllocate(eps->ds,eps->ncv+1));
      49          29 :   PetscFunctionReturn(PETSC_SUCCESS);
      50             : }
      51             : 
      52          29 : static PetscErrorCode EPSSolve_Arnoldi(EPS eps)
      53             : {
      54          29 :   PetscInt           k,nv,ld;
      55          29 :   Mat                U,Op,H;
      56          29 :   PetscScalar        *Harray;
      57          29 :   PetscReal          beta,gamma=1.0;
      58          29 :   PetscBool          breakdown,harmonic,refined;
      59          29 :   BVOrthogRefineType orthog_ref;
      60          29 :   EPS_ARNOLDI        *arnoldi = (EPS_ARNOLDI*)eps->data;
      61             : 
      62          29 :   PetscFunctionBegin;
      63          29 :   PetscCall(DSGetLeadingDimension(eps->ds,&ld));
      64          29 :   PetscCall(DSGetRefined(eps->ds,&refined));
      65          29 :   harmonic = (eps->extraction==EPS_HARMONIC || eps->extraction==EPS_REFINED_HARMONIC)?PETSC_TRUE:PETSC_FALSE;
      66          29 :   PetscCall(BVGetOrthogonalization(eps->V,NULL,&orthog_ref,NULL,NULL));
      67             : 
      68             :   /* Get the starting Arnoldi vector */
      69          29 :   PetscCall(EPSGetStartVector(eps,0,NULL));
      70             : 
      71             :   /* Restart loop */
      72         838 :   while (eps->reason == EPS_CONVERGED_ITERATING) {
      73         809 :     eps->its++;
      74             : 
      75             :     /* Compute an nv-step Arnoldi factorization */
      76         809 :     nv = PetscMin(eps->nconv+eps->mpd,eps->ncv);
      77         809 :     PetscCall(DSSetDimensions(eps->ds,nv,eps->nconv,0));
      78         809 :     if (!arnoldi->delayed) {
      79         773 :       PetscCall(STGetOperator(eps->st,&Op));
      80         773 :       PetscCall(DSGetMat(eps->ds,DS_MAT_A,&H));
      81         773 :       PetscCall(BVMatArnoldi(eps->V,Op,H,eps->nconv,&nv,&beta,&breakdown));
      82         773 :       PetscCall(DSRestoreMat(eps->ds,DS_MAT_A,&H));
      83         773 :       PetscCall(STRestoreOperator(eps->st,&Op));
      84          36 :     } else if (orthog_ref == BV_ORTHOG_REFINE_NEVER) {
      85          18 :       PetscCall(DSGetArray(eps->ds,DS_MAT_A,&Harray));
      86          18 :       PetscCall(EPSDelayedArnoldi1(eps,Harray,ld,eps->nconv,&nv,&beta,&breakdown));
      87          18 :       PetscCall(DSRestoreArray(eps->ds,DS_MAT_A,&Harray));
      88             :     } else {
      89          18 :       PetscCall(DSGetArray(eps->ds,DS_MAT_A,&Harray));
      90          18 :       PetscCall(EPSDelayedArnoldi(eps,Harray,ld,eps->nconv,&nv,&beta,&breakdown));
      91          18 :       PetscCall(DSRestoreArray(eps->ds,DS_MAT_A,&Harray));
      92             :     }
      93         809 :     PetscCall(DSSetState(eps->ds,DS_STATE_INTERMEDIATE));
      94         809 :     PetscCall(BVSetActiveColumns(eps->V,eps->nconv,nv));
      95             : 
      96             :     /* Compute translation of Krylov decomposition if harmonic extraction used */
      97         809 :     if (harmonic) PetscCall(DSTranslateHarmonic(eps->ds,eps->target,beta,PETSC_FALSE,NULL,&gamma));
      98             : 
      99             :     /* Solve projected problem */
     100         809 :     PetscCall(DSSolve(eps->ds,eps->eigr,eps->eigi));
     101         809 :     PetscCall(DSSort(eps->ds,eps->eigr,eps->eigi,NULL,NULL,NULL));
     102         809 :     PetscCall(DSUpdateExtraRow(eps->ds));
     103         809 :     PetscCall(DSSynchronize(eps->ds,eps->eigr,eps->eigi));
     104             : 
     105             :     /* Check convergence */
     106         809 :     PetscCall(EPSKrylovConvergence(eps,PETSC_FALSE,eps->nconv,nv-eps->nconv,beta,0.0,gamma,&k));
     107         809 :     if (refined) {
     108          49 :       PetscCall(DSGetMat(eps->ds,DS_MAT_X,&U));
     109          49 :       PetscCall(BVMultInPlace(eps->V,U,eps->nconv,k+1));
     110          49 :       PetscCall(DSRestoreMat(eps->ds,DS_MAT_X,&U));
     111          49 :       PetscCall(BVOrthonormalizeColumn(eps->V,k,PETSC_FALSE,NULL,NULL));
     112             :     } else {
     113         760 :       PetscCall(DSGetMat(eps->ds,DS_MAT_Q,&U));
     114         760 :       PetscCall(BVMultInPlace(eps->V,U,eps->nconv,PetscMin(k+1,nv)));
     115         760 :       PetscCall(DSRestoreMat(eps->ds,DS_MAT_Q,&U));
     116             :     }
     117         809 :     PetscCall((*eps->stopping)(eps,eps->its,eps->max_it,k,eps->nev,&eps->reason,eps->stoppingctx));
     118         809 :     if (eps->reason == EPS_CONVERGED_ITERATING && breakdown) {
     119           0 :       PetscCall(PetscInfo(eps,"Breakdown in Arnoldi method (it=%" PetscInt_FMT " norm=%g)\n",eps->its,(double)beta));
     120           0 :       PetscCall(EPSGetStartVector(eps,k,&breakdown));
     121           0 :       if (breakdown) {
     122           0 :         eps->reason = EPS_DIVERGED_BREAKDOWN;
     123           0 :         PetscCall(PetscInfo(eps,"Unable to generate more start vectors\n"));
     124             :       }
     125             :     }
     126         809 :     eps->nconv = k;
     127         838 :     PetscCall(EPSMonitor(eps,eps->its,eps->nconv,eps->eigr,eps->eigi,eps->errest,nv));
     128             :   }
     129          29 :   PetscCall(DSTruncate(eps->ds,eps->nconv,PETSC_TRUE));
     130          29 :   PetscFunctionReturn(PETSC_SUCCESS);
     131             : }
     132             : 
     133          21 : static PetscErrorCode EPSSetFromOptions_Arnoldi(EPS eps,PetscOptionItems *PetscOptionsObject)
     134             : {
     135          21 :   PetscBool      set,val;
     136          21 :   EPS_ARNOLDI    *arnoldi = (EPS_ARNOLDI*)eps->data;
     137             : 
     138          21 :   PetscFunctionBegin;
     139          21 :   PetscOptionsHeadBegin(PetscOptionsObject,"EPS Arnoldi Options");
     140             : 
     141          21 :     PetscCall(PetscOptionsBool("-eps_arnoldi_delayed","Use delayed reorthogonalization","EPSArnoldiSetDelayed",arnoldi->delayed,&val,&set));
     142          21 :     if (set) PetscCall(EPSArnoldiSetDelayed(eps,val));
     143             : 
     144          21 :   PetscOptionsHeadEnd();
     145          21 :   PetscFunctionReturn(PETSC_SUCCESS);
     146             : }
     147             : 
     148           4 : static PetscErrorCode EPSArnoldiSetDelayed_Arnoldi(EPS eps,PetscBool delayed)
     149             : {
     150           4 :   EPS_ARNOLDI *arnoldi = (EPS_ARNOLDI*)eps->data;
     151             : 
     152           4 :   PetscFunctionBegin;
     153           4 :   arnoldi->delayed = delayed;
     154           4 :   PetscFunctionReturn(PETSC_SUCCESS);
     155             : }
     156             : 
     157             : /*@
     158             :    EPSArnoldiSetDelayed - Activates or deactivates delayed reorthogonalization
     159             :    in the Arnoldi iteration.
     160             : 
     161             :    Logically Collective
     162             : 
     163             :    Input Parameters:
     164             : +  eps - the eigenproblem solver context
     165             : -  delayed - boolean flag
     166             : 
     167             :    Options Database Key:
     168             : .  -eps_arnoldi_delayed - Activates delayed reorthogonalization in Arnoldi
     169             : 
     170             :    Note:
     171             :    Delayed reorthogonalization is an aggressive optimization for the Arnoldi
     172             :    eigensolver than may provide better scalability, but sometimes makes the
     173             :    solver converge less than the default algorithm.
     174             : 
     175             :    Level: advanced
     176             : 
     177             : .seealso: EPSArnoldiGetDelayed()
     178             : @*/
     179           4 : PetscErrorCode EPSArnoldiSetDelayed(EPS eps,PetscBool delayed)
     180             : {
     181           4 :   PetscFunctionBegin;
     182           4 :   PetscValidHeaderSpecific(eps,EPS_CLASSID,1);
     183          12 :   PetscValidLogicalCollectiveBool(eps,delayed,2);
     184           4 :   PetscTryMethod(eps,"EPSArnoldiSetDelayed_C",(EPS,PetscBool),(eps,delayed));
     185           4 :   PetscFunctionReturn(PETSC_SUCCESS);
     186             : }
     187             : 
     188           5 : static PetscErrorCode EPSArnoldiGetDelayed_Arnoldi(EPS eps,PetscBool *delayed)
     189             : {
     190           5 :   EPS_ARNOLDI *arnoldi = (EPS_ARNOLDI*)eps->data;
     191             : 
     192           5 :   PetscFunctionBegin;
     193           5 :   *delayed = arnoldi->delayed;
     194           5 :   PetscFunctionReturn(PETSC_SUCCESS);
     195             : }
     196             : 
     197             : /*@
     198             :    EPSArnoldiGetDelayed - Gets the type of reorthogonalization used during the Arnoldi
     199             :    iteration.
     200             : 
     201             :    Not Collective
     202             : 
     203             :    Input Parameter:
     204             : .  eps - the eigenproblem solver context
     205             : 
     206             :    Output Parameter:
     207             : .  delayed - boolean flag indicating if delayed reorthogonalization has been enabled
     208             : 
     209             :    Level: advanced
     210             : 
     211             : .seealso: EPSArnoldiSetDelayed()
     212             : @*/
     213           5 : PetscErrorCode EPSArnoldiGetDelayed(EPS eps,PetscBool *delayed)
     214             : {
     215           5 :   PetscFunctionBegin;
     216           5 :   PetscValidHeaderSpecific(eps,EPS_CLASSID,1);
     217           5 :   PetscAssertPointer(delayed,2);
     218           5 :   PetscUseMethod(eps,"EPSArnoldiGetDelayed_C",(EPS,PetscBool*),(eps,delayed));
     219           5 :   PetscFunctionReturn(PETSC_SUCCESS);
     220             : }
     221             : 
     222          22 : static PetscErrorCode EPSDestroy_Arnoldi(EPS eps)
     223             : {
     224          22 :   PetscFunctionBegin;
     225          22 :   PetscCall(PetscFree(eps->data));
     226          22 :   PetscCall(PetscObjectComposeFunction((PetscObject)eps,"EPSArnoldiSetDelayed_C",NULL));
     227          22 :   PetscCall(PetscObjectComposeFunction((PetscObject)eps,"EPSArnoldiGetDelayed_C",NULL));
     228          22 :   PetscFunctionReturn(PETSC_SUCCESS);
     229             : }
     230             : 
     231           0 : static PetscErrorCode EPSView_Arnoldi(EPS eps,PetscViewer viewer)
     232             : {
     233           0 :   PetscBool      isascii;
     234           0 :   EPS_ARNOLDI    *arnoldi = (EPS_ARNOLDI*)eps->data;
     235             : 
     236           0 :   PetscFunctionBegin;
     237           0 :   PetscCall(PetscObjectTypeCompare((PetscObject)viewer,PETSCVIEWERASCII,&isascii));
     238           0 :   if (isascii && arnoldi->delayed) PetscCall(PetscViewerASCIIPrintf(viewer,"  using delayed reorthogonalization\n"));
     239           0 :   PetscFunctionReturn(PETSC_SUCCESS);
     240             : }
     241             : 
     242          22 : SLEPC_EXTERN PetscErrorCode EPSCreate_Arnoldi(EPS eps)
     243             : {
     244          22 :   EPS_ARNOLDI    *ctx;
     245             : 
     246          22 :   PetscFunctionBegin;
     247          22 :   PetscCall(PetscNew(&ctx));
     248          22 :   eps->data = (void*)ctx;
     249             : 
     250          22 :   eps->useds = PETSC_TRUE;
     251             : 
     252          22 :   eps->ops->solve          = EPSSolve_Arnoldi;
     253          22 :   eps->ops->setup          = EPSSetUp_Arnoldi;
     254          22 :   eps->ops->setupsort      = EPSSetUpSort_Default;
     255          22 :   eps->ops->setfromoptions = EPSSetFromOptions_Arnoldi;
     256          22 :   eps->ops->destroy        = EPSDestroy_Arnoldi;
     257          22 :   eps->ops->view           = EPSView_Arnoldi;
     258          22 :   eps->ops->backtransform  = EPSBackTransform_Default;
     259          22 :   eps->ops->computevectors = EPSComputeVectors_Schur;
     260             : 
     261          22 :   PetscCall(PetscObjectComposeFunction((PetscObject)eps,"EPSArnoldiSetDelayed_C",EPSArnoldiSetDelayed_Arnoldi));
     262          22 :   PetscCall(PetscObjectComposeFunction((PetscObject)eps,"EPSArnoldiGetDelayed_C",EPSArnoldiGetDelayed_Arnoldi));
     263          22 :   PetscFunctionReturn(PETSC_SUCCESS);
     264             : }