naginterfaces.library.sparseig.feast_​poly_​gen_​solve

naginterfaces.library.sparseig.feast_poly_gen_solve(handle, irevcm, deg, ze, x, y, m0, d, z, eps, itera, resid, io_manager=None)

feast_poly_gen_solve is an iterative solver used to find some of the eigenvalues and the corresponding eigenvectors of a polynomial eigenvalue problem defined by complex nonsymmetric matrices. This is part of a suite of functions that also includes feast_init(), feast_option(), feast_gen_contour() and feast_custom_contour().

For full information please refer to the NAG Library document for f12jv

https://support.nag.com/numeric/nl/nagdoc_30.2/flhtml/f12/f12jvf.html

Parameters

handleHandle

The handle to the internal data structure used by the NAG FEAST suite. It needs to be initialized by feast_init(). It must not be changed between calls to the NAG FEAST suite.

irevcmint

On initial entry: $irevcm=0$, otherwise an error condition will be raised.

On intermediate entry: must be unchanged from its previous exit value. Changing $irevcm$ to any other value between calls will result in an error.

Note: the matrices $x$, $y$ and $z$ referred to in this section are all of size $n\times m0$ and are stored in the arrays $x$, $y$ and $z$, respectively.

degint

The degree, $p$, of the polynomial eigenvalue problem.

zecomplex

On initial entry: need not be set.

xcomplex, ndarray, shape $(n,2\times \text{m0})$, modified in place

On initial entry: need not be set.

On intermediate exit:

if $irevcm=5$, the calling program must compute $A_{k}z$, storing the result in $x$ prior to re-entry.

If $irevcm=6$, the calling program must compute $A_k^{H}z$, storing the result in $x$ prior to re-entry.

Note: the matrices $x$ and $z$ are stored in the first $m0$ columns of the arrays $x$ and $z$, respectively.

ycomplex, ndarray, shape $(n,\text{m0})$, modified in place

On initial entry: need not be set.

On intermediate exit:

if $irevcm=2$, the calling program must compute the solution to the linear system $\left({\sum }_{i=0}^p{ze}^i{A}_i\right)w=y$, overwriting $y$ with the result $w$, prior to re-entry. The linear system has $m0$ right-hand sides.

If $irevcm=4$, the calling program must compute the solution to the linear system ${\left({\sum }_{i=0}^p{ze}^i{A}_i\right)}^{H}w=y$, overwriting $y$ with the result $w$, prior to re-entry. The linear system has $m0$ right-hand sides.

m0int

On initial entry: the size of the search subspace used to find the eigenvalues. This should exceed the number of eigenvalues within the search contour. See Further Comments for further details.

On intermediate entry: $m0$ must remain unchanged.

dcomplex, ndarray, shape $\left(\text{m0}\right)$, modified in place

On initial entry: if the option $\text{‘Subspace'}=\text{'Yes'}$ was set using the option setting function feast_option(), then $d$ should contain an initial guess at the eigenvalues lying within the eigenvector search subspace (this subspace should be specified by $z$), otherwise $d$ need not be set.

On final exit: the first $nconv$ entries in $d$ contain the eigenvalues.

Note: if the option $\text{‘Subspace'}=\text{'Yes'}$ was set using the option setting function feast_option(), then on final exit $d$ contains an estimate of the eigenvalues after a single contour integral.

zcomplex, ndarray, shape $(n,2\times \text{m0})$, modified in place

On initial entry: if the option $\text{‘Subspace'}=\text{'Yes'}$ was set using the option setting function feast_option(), then $z$ should contain an initial guess at the eigenvector search subspace, otherwise $z$ need not be set.

Note: if the option $\text{‘Subspace'}=\text{'Yes'}$ was set but only right eigenvectors are to be computed, then only the first $m0$ columns of $z$ need to be set. However, if the option $\text{‘Eigenvectors'}=\text{'Two-sided'}$ was set using feast_option(), so that both left and right eigenvectors are returned, then the first $m0$ columns of $z$ should contain the initial guess for the right eigenvector search subspace and the remaining $m0$ columns should contain an initial guess for the left eigenvector search subspace.

On intermediate exit: must not be changed.

On final exit: the first $nconv$ columns of $z$ contain the right eigenvectors corresponding to the eigenvalues found within the contour. If the option $\text{‘Eigenvectors'}=\text{'Two-sided'}$ was set in the option setting function feast_option(), the columns $m0+1:m0+nconv$ of $z$ contain the left eigenvectors corresponding to the eigenvalues found within the contour.

Note: if the option $\text{‘Execution Mode'}=\text{'Subspace'}$ was set using the option setting function feast_option(), then on final exit columns $1:m0$ of $z$ contain the current search subspace after one contour integral.

epsfloat

On initial entry: need not be set.

iteraint

On initial entry: need not be set.

residfloat, ndarray, shape $(2\times \text{m0})$, modified in place

On initial entry: need not be set.

On final exit: for $i=1,\dots ,nconv$, $resid[i-1]$ contains the relative residual, in the $1$-norm, of the $i$th eigenpair found, that is $resid[i-1]=\Vert \left({\sum }_{j=0}^p{\lambda }_i^j{A}_j\right)z_i\Vert /(\parallel {\lambda }^p{A}_p{z}_i\parallel \times (\left|E_{mid}\right|+r))$, where $E_{mid}$ is the centre of mass of the contour and $r$ is the radius of the circle, centred at $E_{mid}$ which just encloses the contour.

If the option $\text{‘Eigenvectors'}=\text{'Two-sided'}$ was set in the option setting function feast_option(), the entries $m0+1:m0+nconv$ of $resid$ contain corresponding residuals for the left eigenvectors, $resid[i-1]=\Vert {\left({\sum }_{j=0}^p{\lambda }_i^j{A}_j\right)}^H{z}_i\Vert /(\Vert {\lambda }^p{A}_p^H{z}_i\Vert \times (\left|E_{mid}\right|+r))$.

io_managerFileObjManager, optional

Manager for I/O in this routine.

Returns

irevcmint

On intermediate exit: has the following meanings.

$irevcm=1$

The calling program must compute a factorization of the matrix ${\sum }_{i=0}^p{ze}^i{A}_i$ suitable for solving a linear system, for example using sparse.complex_gen_precon_ilu which computes an incomplete $LU$ factorization of a complex sparse matrix. All arguments to the routine must remain unchanged.

Note: the factorization can be computed in single precision.

$irevcm=2$

The calling program must compute the solution to the linear system $\left({\sum }_{i=0}^p{ze}^i{A}_i\right)w=y$, overwriting $y$ with the result $w$. The matrix ${\sum }_{i=0}^p{ze}^i{A}_i$ has previously been factorized (when $irevcm=1$ was returned) and this factorization can be reused here.

Note: the solve can be performed in single precision.

$irevcm=3$

Optionally, the calling program must compute a factorization of the matrix ${\left({\sum }_{i=0}^p{ze}^i{A}_i\right)}^H$. This need only be done if it is not possible to use the factorization computed when $irevcm=1$ was returned to solve linear systems involving ${\left({\sum }_{i=0}^p{ze}^i{A}_i\right)}^H$. If this factorization is to be computed, then the factorization from $irevcm=1$ must not be overwritten.

Note: the factorization can be performed in single precision.

$irevcm=4$

The calling program must compute the solution to the linear system ${\left({\sum }_{i=0}^p{ze}^i{A}_i\right)}^{H}w=y$, overwriting $y$ with the result $w$. If it is not possible to use the factorization of ${\sum }_{i=0}^p{ze}^i{A}_i$ (computed when $irevcm=1$ was returned) then the factorization of ${\left({\sum }_{i=0}^p{ze}^i{A}_i\right)}^H$ (computed when $irevcm=2$ was returned) should be used here.

Note: the factorization can be performed in single precision.

$irevcm=5$

The calling program must compute $A_{k}z$, storing the result in $x$.

$irevcm=6$

The calling program must compute $A_k^{H}z$, storing the result in $x$.

On final exit: $irevcm=0$: feast_poly_gen_solve has completed its tasks. The value of $\text{errno}$ determines whether the iteration has been successfully completed, or whether errors have been detected.

Note: the matrices $x$, $y$ and $z$ referred to in this section are all of size $n\times m0$ and are stored in the arrays $x$, $y$ and $z$, respectively.

zecomplex

On intermediate exit: contains the current point on the contour.

If $irevcm=1$, then this must be used by the calling program to form a factorization of the matrix ${\sum }_{i=0}^p{ze}^i{A}_i$.

If $irevcm=3$, then, optionally, this can be used to form a factorization of ${\left({\sum }_{i=0}^p{ze}^i{A}_i\right)}^H$.

kint

On intermediate exit:

if $irevcm=5$, denotes which of the coefficient matrices $A_k$ needs to be used to form $A_{k}z$.

If $irevcm=6$, denotes which of the coefficient matrices $A_k$ needs to be used to form $A_k^{H}z$.

m0int

If the initial search subspace was found by feast_poly_gen_solve to be too large, then a new smaller suitable choice is returned.

nconvint

The number of eigenvalues found within the search contour.

epsfloat

The relative error on the trace. At iteration $k$, $eps$ is given by the expression $|{\text{trace}}_k-{\text{trace}}_{k-1}|/(\left|E_{mid}\right|+r)$, where ${\text{trace}}_k$ is the sum of the eigenvalues found at the $k$th iteration, $E_{mid}$ is the centre of mass of the contour and $r$ is the radius of the circle, centred at $E_{mid}$ which just encloses the contour.

iteraint

The number of subspace iterations performed.

Raises

NagValueError

(errno $1$)

Either one of the contour setting functions feast_gen_contour() or feast_custom_contour() has not been called prior to the first call of this function or the supplied $handle$ has become corrupted.

(errno $7$)

An internal error occurred in the reduced eigenvalue solver. Please contact NAG.

(errno $8$)

On entry, $n=⟨value⟩$.

Constraint: $n\ge 1$.

(errno $9$)

On entry, $m0=⟨value⟩$ and $n=⟨value⟩$.

Constraint: $0<m0\le n$.

(errno $13$)

On initial entry, $irevcm=⟨value⟩$.

Constraint: $irevcm=0$.

(errno $13$)

On intermediate entry, $irevcm=⟨value⟩$.

Constraint: $irevcm=1$, $2$, $3$, $4$, $5$ or $6$.

(errno $14$)

On entry, $deg=⟨value⟩$.

Constraint: $deg>0$.

(errno $15$)

The option $\text{‘Subspace'}=\text{'Yes'}$ was set using the option setting function feast_option() but no nonzero elements were found in the supplied subspace.

Warns

NagAlgorithmicWarning

(errno $2$)

No eigenvalues were found within the search contour.

(errno $3$)

The function did not converge after the maximum number of iterations.

(errno $4$)

The size of the eigenvector search subspace, $m0$, is too small.

(errno $5$)

The option $\text{‘Execution Mode'}=\text{'Subspace'}$ was set using feast_option(). Columns $1:m0$ of $z$ contain the search subspace after one contour integral and $d$ contains an estimate of the eigenvalues.

(errno $6$)

The option $\text{‘Execution Mode'}=\text{'Estimate'}$ was set using feast_option(). $nconv$ contains a stochastic estimate of the number of eigenvalues within the contour.

Notes

The suite of functions is designed to calculate some of the eigenvalues, $\lambda$, and the corresponding eigenvectors, $x$, of a polynomial eigenvalue problem ${\sum }_{i=0}^p{\lambda }^i{A}_{i}x=0$ where the coefficient matrices $A_i$ are sparse, complex and nonsymmetric. The suite can also be used to find selected eigenvalues/eigenvectors of smaller scale, dense problems.

feast_poly_gen_solve is a reverse communication function, based on the FEAST eigensolver, described in Polizzi (2009), which finds eigenvalues using contour integration. Prior to calling feast_poly_gen_solve, one of the contour definition functions feast_gen_contour() or feast_custom_contour() must be used to define nodes and weights for a contour around a region in the complex plane within which eigenvalues will be sought. feast_gen_contour() or feast_custom_contour() uses this interval to define nodes and weights for the contour to be used by feast_poly_gen_solve.

The setup function feast_init() and one of the contour definition functions feast_gen_contour() or feast_custom_contour() must be called before feast_poly_gen_solve. Between the calls to feast_init() and feast_gen_contour() or feast_custom_contour(), options may be set by calls to the option setting function feast_option().

feast_poly_gen_solve uses reverse communication, i.e., it returns repeatedly to the calling program with the argument $irevcm$ (see Parameters) set to specified values which require the calling program to carry out one of the following tasks:

• compute a factorization of the matrix ${\sum }_{i=0}^p{ze}^i{A}_i$, where $ze$ is a point on the search contour;

• optionally, compute a factorization of the matrix ${\left({\sum }_{i=0}^p{ze}^i{A}_i\right)}^H$ (this need only be done if the factorization ${\sum }_{i=0}^p{ze}^i{A}_i$ does not allow linear systems involving ${\left({\sum }_{i=0}^p{ze}^i{A}_i\right)}^H$ to be solved);

• solve a linear system involving ${\sum }_{i=0}^p{ze}^i{A}_i$ or ${\left({\sum }_{i=0}^p{ze}^i{A}_i\right)}^H$, using the factorizations above;

• compute the matrix product $x=A_{k}z$, for a given value of $k$;

• compute the matrix product $x=A_k^{H}z$, for a given value of $k$;

• notify the completion of the computation.

The number of contour points, the number of iterations, and other options can all be set using the option setting function feast_option() (see Other Parameters for feast_option for details on setting options and of the default settings). The search contour itself is defined by a call to feast_gen_contour() or feast_custom_contour().

References

Gavin, B, Międlar, A and Polizzi, E, 2018, FEAST Eigensolver for Nonlinear Eigenvalue Problems, J. Comput. Phys. (27), 107

Polizzi, E, 2009, Density-Matrix-Based Algorithms for Solving Eigenvalue Problems, Phys. Rev. B. (79), 115112

See also

naginterfaces.library.examples.sparseig.feast_poly_gen_solve_ex.main()