/*
|
/*
|
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
|
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
|
SLEPc - Scalable Library for Eigenvalue Problem Computations
|
SLEPc - Scalable Library for Eigenvalue Problem Computations
|
Copyright (c) 2002-2010, Universidad Politecnica de Valencia, Spain
|
Copyright (c) 2002-2011, Universitat Politecnica de Valencia, Spain
|
|
|
This file is part of SLEPc.
|
This file is part of SLEPc.
|
|
|
SLEPc is free software: you can redistribute it and/or modify it under the
|
SLEPc is free software: you can redistribute it and/or modify it under the
|
terms of version 3 of the GNU Lesser General Public License as published by
|
terms of version 3 of the GNU Lesser General Public License as published by
|
the Free Software Foundation.
|
the Free Software Foundation.
|
|
|
SLEPc is distributed in the hope that it will be useful, but WITHOUT ANY
|
SLEPc is distributed in the hope that it will be useful, but WITHOUT ANY
|
WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
|
WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
|
FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for
|
FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for
|
more details.
|
more details.
|
|
|
You should have received a copy of the GNU Lesser General Public License
|
You should have received a copy of the GNU Lesser General Public License
|
along with SLEPc. If not, see <http://www.gnu.org/licenses/>.
|
along with SLEPc. If not, see <http://www.gnu.org/licenses/>.
|
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
|
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
|
*/
|
*/
|
|
|
static char help[] = "Eigenvalue problem associated with a Markov model of a random walk on a triangular grid. "
|
static char help[] = "Eigenvalue problem associated with a Markov model of a random walk on a triangular grid. "
|
"It is a standard nonsymmetric eigenproblem with real eigenvalues and the rightmost eigenvalue is known to be 1.\n"
|
"It is a standard nonsymmetric eigenproblem with real eigenvalues and the rightmost eigenvalue is known to be 1.\n"
|
"This example illustrates how the user can set the initial vector.\n\n"
|
"This example illustrates how the user can set the initial vector.\n\n"
|
"The command line options are:\n"
|
"The command line options are:\n"
|
" -m <m>, where <m> = number of grid subdivisions in each dimension.\n\n";
|
" -m <m>, where <m> = number of grid subdivisions in each dimension.\n\n";
|
|
|
#include <slepceps.h>
|
#include <slepceps.h>
|
|
|
/*
|
/*
|
User-defined routines
|
User-defined routines
|
*/
|
*/
|
PetscErrorCode MatMarkovModel(PetscInt m,Mat A);
|
PetscErrorCode MatMarkovModel(PetscInt m,Mat A);
|
PetscErrorCode MyEigenSort(EPS eps,PetscScalar ar,PetscScalar ai,PetscScalar br,PetscScalar bi,PetscInt *r,void *ctx);
|
PetscErrorCode MyEigenSort(EPS eps,PetscScalar ar,PetscScalar ai,PetscScalar br,PetscScalar bi,PetscInt *r,void *ctx);
|
|
|
#undef __FUNCT__
|
#undef __FUNCT__
|
#define __FUNCT__ "main"
|
#define __FUNCT__ "main"
|
int main(int argc,char **argv)
|
int main(int argc,char **argv)
|
{
|
{
|
Vec v0; /* initial vector */
|
Vec v0; /* initial vector */
|
Mat A; /* operator matrix */
|
Mat A; /* operator matrix */
|
EPS eps; /* eigenproblem solver context */
|
EPS eps; /* eigenproblem solver context */
|
const EPSType type;
|
const EPSType type;
|
PetscReal tol=1000*PETSC_MACHINE_EPSILON;
|
PetscReal tol=1000*PETSC_MACHINE_EPSILON;
|
PetscInt N,m=15,nev,maxit;
|
PetscInt N,m=15,nev,maxit;
|
PetscScalar origin=0.0;
|
PetscScalar origin=0.0;
|
PetscErrorCode ierr;
|
PetscErrorCode ierr;
|
|
|
SlepcInitialize(&argc,&argv,(char*)0,help);
|
SlepcInitialize(&argc,&argv,(char*)0,help);
|
|
|
ierr = PetscOptionsGetInt(PETSC_NULL,"-m",&m,PETSC_NULL);CHKERRQ(ierr);
|
ierr = PetscOptionsGetInt(PETSC_NULL,"-m",&m,PETSC_NULL);CHKERRQ(ierr);
|
N = m*(m+1)/2;
|
N = m*(m+1)/2;
|
ierr = PetscPrintf(PETSC_COMM_WORLD,"\nMarkov Model, N=%D (m=%D)\n\n",N,m);CHKERRQ(ierr);
|
ierr = PetscPrintf(PETSC_COMM_WORLD,"\nMarkov Model, N=%D (m=%D)\n\n",N,m);CHKERRQ(ierr);
|
|
|
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
|
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
|
Compute the operator matrix that defines the eigensystem, Ax=kx
|
Compute the operator matrix that defines the eigensystem, Ax=kx
|
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
|
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
|
|
|
ierr = MatCreate(PETSC_COMM_WORLD,&A);CHKERRQ(ierr);
|
ierr = MatCreate(PETSC_COMM_WORLD,&A);CHKERRQ(ierr);
|
ierr = MatSetSizes(A,PETSC_DECIDE,PETSC_DECIDE,N,N);CHKERRQ(ierr);
|
ierr = MatSetSizes(A,PETSC_DECIDE,PETSC_DECIDE,N,N);CHKERRQ(ierr);
|
ierr = MatSetFromOptions(A);CHKERRQ(ierr);
|
ierr = MatSetFromOptions(A);CHKERRQ(ierr);
|
ierr = MatMarkovModel(m,A);CHKERRQ(ierr);
|
ierr = MatMarkovModel(m,A);CHKERRQ(ierr);
|
|
|
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
|
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
|
Create the eigensolver and set various options
|
Create the eigensolver and set various options
|
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
|
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
|
|
|
/*
|
/*
|
Create eigensolver context
|
Create eigensolver context
|
*/
|
*/
|
ierr = EPSCreate(PETSC_COMM_WORLD,&eps);CHKERRQ(ierr);
|
ierr = EPSCreate(PETSC_COMM_WORLD,&eps);CHKERRQ(ierr);
|
|
|
/*
|
/*
|
Set operators. In this case, it is a standard eigenvalue problem
|
Set operators. In this case, it is a standard eigenvalue problem
|
*/
|
*/
|
ierr = EPSSetOperators(eps,A,PETSC_NULL);CHKERRQ(ierr);
|
ierr = EPSSetOperators(eps,A,PETSC_NULL);CHKERRQ(ierr);
|
ierr = EPSSetProblemType(eps,EPS_NHEP);CHKERRQ(ierr);
|
ierr = EPSSetProblemType(eps,EPS_NHEP);CHKERRQ(ierr);
|
ierr = EPSSetTolerances(eps,tol,PETSC_DECIDE);CHKERRQ(ierr);
|
ierr = EPSSetTolerances(eps,tol,PETSC_DECIDE);CHKERRQ(ierr);
|
|
|
/*
|
/*
|
Set the custom comparing routine in order to obtain the eigenvalues
|
Set the custom comparing routine in order to obtain the eigenvalues
|
closest to the target on the right only
|
closest to the target on the right only
|
*/
|
*/
|
ierr = EPSSetEigenvalueComparison(eps,MyEigenSort,&origin);CHKERRQ(ierr);
|
ierr = EPSSetEigenvalueComparison(eps,MyEigenSort,&origin);CHKERRQ(ierr);
|
|
|
|
|
/*
|
/*
|
Set solver parameters at runtime
|
Set solver parameters at runtime
|
*/
|
*/
|
ierr = EPSSetFromOptions(eps);CHKERRQ(ierr);
|
ierr = EPSSetFromOptions(eps);CHKERRQ(ierr);
|
|
|
/*
|
/*
|
Set the initial vector. This is optional, if not done the initial
|
Set the initial vector. This is optional, if not done the initial
|
vector is set to random values
|
vector is set to random values
|
*/
|
*/
|
ierr = MatGetVecs(A,&v0,PETSC_NULL);CHKERRQ(ierr);
|
ierr = MatGetVecs(A,&v0,PETSC_NULL);CHKERRQ(ierr);
|
ierr = VecSet(v0,1.0);CHKERRQ(ierr);
|
ierr = VecSet(v0,1.0);CHKERRQ(ierr);
|
ierr = EPSSetInitialSpace(eps,1,&v0);CHKERRQ(ierr);
|
ierr = EPSSetInitialSpace(eps,1,&v0);CHKERRQ(ierr);
|
|
|
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
|
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
|
Solve the eigensystem
|
Solve the eigensystem
|
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
|
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
|
|
|
ierr = EPSSolve(eps);CHKERRQ(ierr);
|
ierr = EPSSolve(eps);CHKERRQ(ierr);
|
|
|
/*
|
/*
|
Optional: Get some information from the solver and display it
|
Optional: Get some information from the solver and display it
|
*/
|
*/
|
ierr = EPSGetType(eps,&type);CHKERRQ(ierr);
|
ierr = EPSGetType(eps,&type);CHKERRQ(ierr);
|
ierr = PetscPrintf(PETSC_COMM_WORLD," Solution method: %s\n\n",type);CHKERRQ(ierr);
|
ierr = PetscPrintf(PETSC_COMM_WORLD," Solution method: %s\n\n",type);CHKERRQ(ierr);
|
ierr = EPSGetDimensions(eps,&nev,PETSC_NULL,PETSC_NULL);CHKERRQ(ierr);
|
ierr = EPSGetDimensions(eps,&nev,PETSC_NULL,PETSC_NULL);CHKERRQ(ierr);
|
ierr = PetscPrintf(PETSC_COMM_WORLD," Number of requested eigenvalues: %D\n",nev);CHKERRQ(ierr);
|
ierr = PetscPrintf(PETSC_COMM_WORLD," Number of requested eigenvalues: %D\n",nev);CHKERRQ(ierr);
|
ierr = EPSGetTolerances(eps,&tol,&maxit);CHKERRQ(ierr);
|
ierr = EPSGetTolerances(eps,&tol,&maxit);CHKERRQ(ierr);
|
ierr = PetscPrintf(PETSC_COMM_WORLD," Stopping condition: tol=%.4G, maxit=%D\n",tol,maxit);CHKERRQ(ierr);
|
ierr = PetscPrintf(PETSC_COMM_WORLD," Stopping condition: tol=%.4G, maxit=%D\n",tol,maxit);CHKERRQ(ierr);
|
|
|
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
|
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
|
Display solution and clean up
|
Display solution and clean up
|
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
|
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
|
|
|
ierr = EPSPrintSolution(eps,PETSC_NULL);CHKERRQ(ierr);
|
ierr = EPSPrintSolution(eps,PETSC_NULL);CHKERRQ(ierr);
|
ierr = EPSDestroy(&eps);CHKERRQ(ierr);
|
ierr = EPSDestroy(&eps);CHKERRQ(ierr);
|
ierr = MatDestroy(&A);CHKERRQ(ierr);
|
ierr = MatDestroy(&A);CHKERRQ(ierr);
|
ierr = VecDestroy(&v0);CHKERRQ(ierr);
|
ierr = VecDestroy(&v0);CHKERRQ(ierr);
|
ierr = SlepcFinalize();CHKERRQ(ierr);
|
ierr = SlepcFinalize();CHKERRQ(ierr);
|
return 0;
|
return 0;
|
}
|
}
|
|
|
#undef __FUNCT__
|
#undef __FUNCT__
|
#define __FUNCT__ "MatMarkovModel"
|
#define __FUNCT__ "MatMarkovModel"
|
/*
|
/*
|
Matrix generator for a Markov model of a random walk on a triangular grid.
|
Matrix generator for a Markov model of a random walk on a triangular grid.
|
|
|
This subroutine generates a test matrix that models a random walk on a
|
This subroutine generates a test matrix that models a random walk on a
|
triangular grid. This test example was used by G. W. Stewart ["{SRRIT} - a
|
triangular grid. This test example was used by G. W. Stewart ["{SRRIT} - a
|
FORTRAN subroutine to calculate the dominant invariant subspaces of a real
|
FORTRAN subroutine to calculate the dominant invariant subspaces of a real
|
matrix", Tech. report. TR-514, University of Maryland (1978).] and in a few
|
matrix", Tech. report. TR-514, University of Maryland (1978).] and in a few
|
papers on eigenvalue problems by Y. Saad [see e.g. LAA, vol. 34, pp. 269-295
|
papers on eigenvalue problems by Y. Saad [see e.g. LAA, vol. 34, pp. 269-295
|
(1980) ]. These matrices provide reasonably easy test problems for eigenvalue
|
(1980) ]. These matrices provide reasonably easy test problems for eigenvalue
|
algorithms. The transpose of the matrix is stochastic and so it is known
|
algorithms. The transpose of the matrix is stochastic and so it is known
|
that one is an exact eigenvalue. One seeks the eigenvector of the transpose
|
that one is an exact eigenvalue. One seeks the eigenvector of the transpose
|
associated with the eigenvalue unity. The problem is to calculate the steady
|
associated with the eigenvalue unity. The problem is to calculate the steady
|
state probability distribution of the system, which is the eigevector
|
state probability distribution of the system, which is the eigevector
|
associated with the eigenvalue one and scaled in such a way that the sum all
|
associated with the eigenvalue one and scaled in such a way that the sum all
|
the components is equal to one.
|
the components is equal to one.
|
|
|
Note: the code will actually compute the transpose of the stochastic matrix
|
Note: the code will actually compute the transpose of the stochastic matrix
|
that contains the transition probabilities.
|
that contains the transition probabilities.
|
*/
|
*/
|
PetscErrorCode MatMarkovModel(PetscInt m,Mat A)
|
PetscErrorCode MatMarkovModel(PetscInt m,Mat A)
|
{
|
{
|
const PetscReal cst = 0.5/(PetscReal)(m-1);
|
const PetscReal cst = 0.5/(PetscReal)(m-1);
|
PetscReal pd,pu;
|
PetscReal pd,pu;
|
PetscInt Istart,Iend,i,j,jmax,ix=0;
|
PetscInt Istart,Iend,i,j,jmax,ix=0;
|
PetscErrorCode ierr;
|
PetscErrorCode ierr;
|
|
|
PetscFunctionBegin;
|
PetscFunctionBegin;
|
ierr = MatGetOwnershipRange(A,&Istart,&Iend);CHKERRQ(ierr);
|
ierr = MatGetOwnershipRange(A,&Istart,&Iend);CHKERRQ(ierr);
|
for (i=1;i<=m;i++) {
|
for (i=1;i<=m;i++) {
|
jmax = m-i+1;
|
jmax = m-i+1;
|
for (j=1;j<=jmax;j++) {
|
for (j=1;j<=jmax;j++) {
|
ix = ix + 1;
|
ix = ix + 1;
|
if (ix-1<Istart || ix>Iend) continue; /* compute only owned rows */
|
if (ix-1<Istart || ix>Iend) continue; /* compute only owned rows */
|
if (j!=jmax) {
|
if (j!=jmax) {
|
pd = cst*(PetscReal)(i+j-1);
|
pd = cst*(PetscReal)(i+j-1);
|
/* north */
|
/* north */
|
if (i==1) {
|
if (i==1) {
|
ierr = MatSetValue(A,ix-1,ix,2*pd,INSERT_VALUES);CHKERRQ(ierr);
|
ierr = MatSetValue(A,ix-1,ix,2*pd,INSERT_VALUES);CHKERRQ(ierr);
|
} else {
|
} else {
|
ierr = MatSetValue(A,ix-1,ix,pd,INSERT_VALUES);CHKERRQ(ierr);
|
ierr = MatSetValue(A,ix-1,ix,pd,INSERT_VALUES);CHKERRQ(ierr);
|
}
|
}
|
/* east */
|
/* east */
|
if (j==1) {
|
if (j==1) {
|
ierr = MatSetValue(A,ix-1,ix+jmax-1,2*pd,INSERT_VALUES);CHKERRQ(ierr);
|
ierr = MatSetValue(A,ix-1,ix+jmax-1,2*pd,INSERT_VALUES);CHKERRQ(ierr);
|
} else {
|
} else {
|
ierr = MatSetValue(A,ix-1,ix+jmax-1,pd,INSERT_VALUES);CHKERRQ(ierr);
|
ierr = MatSetValue(A,ix-1,ix+jmax-1,pd,INSERT_VALUES);CHKERRQ(ierr);
|
}
|
}
|
}
|
}
|
/* south */
|
/* south */
|
pu = 0.5 - cst*(PetscReal)(i+j-3);
|
pu = 0.5 - cst*(PetscReal)(i+j-3);
|
if (j>1) {
|
if (j>1) {
|
ierr = MatSetValue(A,ix-1,ix-2,pu,INSERT_VALUES);CHKERRQ(ierr);
|
ierr = MatSetValue(A,ix-1,ix-2,pu,INSERT_VALUES);CHKERRQ(ierr);
|
}
|
}
|
/* west */
|
/* west */
|
if (i>1) {
|
if (i>1) {
|
ierr = MatSetValue(A,ix-1,ix-jmax-2,pu,INSERT_VALUES);CHKERRQ(ierr);
|
ierr = MatSetValue(A,ix-1,ix-jmax-2,pu,INSERT_VALUES);CHKERRQ(ierr);
|
}
|
}
|
}
|
}
|
}
|
}
|
ierr = MatAssemblyBegin(A,MAT_FINAL_ASSEMBLY);CHKERRQ(ierr);
|
ierr = MatAssemblyBegin(A,MAT_FINAL_ASSEMBLY);CHKERRQ(ierr);
|
ierr = MatAssemblyEnd(A,MAT_FINAL_ASSEMBLY);CHKERRQ(ierr);
|
ierr = MatAssemblyEnd(A,MAT_FINAL_ASSEMBLY);CHKERRQ(ierr);
|
PetscFunctionReturn(0);
|
PetscFunctionReturn(0);
|
}
|
}
|
|
|
#undef __FUNCT__
|
#undef __FUNCT__
|
#define __FUNCT__ "MyEigenSort"
|
#define __FUNCT__ "MyEigenSort"
|
/*
|
/*
|
Function for user-defined eigenvalue ordering criterion.
|
Function for user-defined eigenvalue ordering criterion.
|
|
|
Given two eigenvalues ar+i*ai and br+i*bi, the subroutine must choose
|
Given two eigenvalues ar+i*ai and br+i*bi, the subroutine must choose
|
one of them as the preferred one according to the criterion.
|
one of them as the preferred one according to the criterion.
|
In this example, the preferred value is the one furthest to the origin.
|
In this example, the preferred value is the one furthest to the origin.
|
*/
|
*/
|
PetscErrorCode MyEigenSort(EPS eps,PetscScalar ar,PetscScalar ai,PetscScalar br,PetscScalar bi,PetscInt *r,void *ctx)
|
PetscErrorCode MyEigenSort(EPS eps,PetscScalar ar,PetscScalar ai,PetscScalar br,PetscScalar bi,PetscInt *r,void *ctx)
|
{
|
{
|
PetscScalar origin = *(PetscScalar*)ctx;
|
PetscScalar origin = *(PetscScalar*)ctx;
|
PetscReal d;
|
PetscReal d;
|
|
|
PetscFunctionBegin;
|
PetscFunctionBegin;
|
d = (SlepcAbsEigenvalue(br-origin,bi) - SlepcAbsEigenvalue(ar-origin,ai))/PetscMax(SlepcAbsEigenvalue(ar-origin,ai),SlepcAbsEigenvalue(br-origin,bi));
|
d = (SlepcAbsEigenvalue(br-origin,bi) - SlepcAbsEigenvalue(ar-origin,ai))/PetscMax(SlepcAbsEigenvalue(ar-origin,ai),SlepcAbsEigenvalue(br-origin,bi));
|
*r = d > PETSC_SQRT_MACHINE_EPSILON ? 1 : (d < -PETSC_SQRT_MACHINE_EPSILON ? -1 : PetscSign(PetscRealPart(br)));
|
*r = d > PETSC_SQRT_MACHINE_EPSILON ? 1 : (d < -PETSC_SQRT_MACHINE_EPSILON ? -1 : PetscSign(PetscRealPart(br)));
|
PetscFunctionReturn(0);
|
PetscFunctionReturn(0);
|
}
|
}
|
|
|
|
|