SPEIGS 1.0.0
Functions | Variables
speigs.c File Reference

The implementation of sparse eigen decomposition routine for HDSDP. More...

#include <stdio.h>
#include <math.h>
#include <string.h>
#include "speigs.h"
#include "spinfo.h"

Functions

static void speig_get_factorize_space (spint *n, spint *sn, spint *type, spint *liwork, spint *lwork)
 Compute lwork and iwork. More...
 
static void speigs_is_diag (spint *p, spint *i, spint n, spint *is_diag)
 Check if a matrix is diagonal. More...
 
static void speigs_is_rankone (spint *p, spint *i, double *x, spint n, spint *is_rankone, double *work, double tol)
 Find out if a matrix is rank-one. $ A = \alpha a a^T $. More...
 
static void speigs_compute_submat (spint *p, spint *i, spint n, spint *sn, spint *nnzs, spint *perm, spint *iperm)
 Compute the dense submatrix of a large sparse matrix. More...
 
static spint speigs_factorize_zero (spint *p, spint *i, double *x, spint n, spint *aiwork, double *awork, spint *sn, spint *iwork, spint *liwork, double *work, spint *lwork, double *evals, double *evecs, spint *rank, double tol)
 Compute the eigen factorization of an all-zero matrix. More...
 
static spint speigs_factorize_diag (spint *p, spint *i, double *x, spint n, spint *aiwork, double *awork, spint *sn, spint *iwork, spint *liwork, double *work, spint *lwork, double *evals, double *evecs, spint *rank, double tol)
 Compute the eigen factorization of a diagonal matrix. More...
 
static spint speigs_factorize_two (spint *p, spint *i, double *x, spint n, spint *aiwork, double *awork, spint *sn, spint *iwork, spint *liwork, double *work, spint *lwork, double *evals, double *evecs, spint *rank, double tol)
 Compute the eigen factorization of a two-two matrix. More...
 
static spint speigs_factorize_rankone (spint *p, spint *i, double *x, spint n, spint *aiwork, double *awork, spint *sn, spint *iwork, spint *liwork, double *work, spint *lwork, double *evals, double *evecs, spint *rank, double tol)
 Compute the eigen factorization of a rank-one matrix. More...
 
static spint speigs_factorize_dense (double *a, double *evals, double *evecs, spint *n, spint *liwork, spint *iwork, spint *lwork, double *work, spint *isuppz)
 Compute the eigen factorization of a general full matrix. More...
 
static spint speigs_factorize_sparse (spint *p, spint *i, double *x, spint n, spint *aiwork, double *awork, spint *sn, spint *iwork, spint *liwork, double *work, spint *lwork, double *evals, double *evecs, spint *rank, double tol)
 Compute the eigen factorization of a sparse matrix admitting an easier submatrix representation. More...
 
static spint speigs_factorize_general (spint *p, spint *i, double *x, spint n, spint *aiwork, double *awork, spint *sn, spint *iwork, spint *liwork, double *work, spint *lwork, double *evals, double *evecs, spint *rank, double tol)
 Compute the eigen factorization of a general dense matrix. More...
 
spint speigs_analyze (spint *Ap, spint *Ai, double *Ax, spint *dim, spint *iwork, spint *liwork, double *work, spint *lwork, spint *type, spint *sn, double tol, double gthresh)
 Perform the analysis phase of sparse eigen-value factorization. More...
 
spint speigs_factorize (spint *Ap, spint *Ai, double *Ax, spint *dim, spint *aiwork, double *awork, spint *type, spint *sn, spint *iwork, spint *liwork, double *work, spint *lwork, double *evals, double *evecs, spint *rank, double tol)
 Perform the analysis phase of sparse eigen-value factorization. More...
 

Variables

static char jobz = 'V'
 
static char range = 'A'
 
static char uplolow = 'L'
 
static double abstol = 0.0
 
static spint(* speig_routines [6])(spint *, spint *, double *, spint, spint *, double *, spint *, spint *, spint *, double *, spint *, double *, double *, spint *, double)
 The jump table for eigen routines. More...
 

Detailed Description

The implementation of sparse eigen decomposition routine for HDSDP.

A set of routines that factorize very sparse matrices that typically arise from semi-definite programming problems. The routines detect the special structures of the matrix and accelerate the factorization procedure.

Author
Wenzhi Gao, Shanghai University of Finance and Economics
Date
Aug, 24th, 2022

Function Documentation

◆ speig_get_factorize_space()

static void speig_get_factorize_space ( spint *  n,
spint *  sn,
spint *  type,
spint *  liwork,
spint *  lwork 
)
static

Compute lwork and iwork.

Parameters
[in]nDimension of the matrix
[in]snDimension of the submatrix
[in]typeType of the matrix
[out]liworkEstimated integer workspace length
[out]lworkEstimated double workspace length

The function computes the space requirement for the subroutines that will be invoked in the factorization phase

◆ speigs_analyze()

spint speigs_analyze ( spint *  Ap,
spint *  Ai,
double *  Ax,
spint *  dim,
spint *  iwork,
spint *  liwork,
double *  work,
spint *  lwork,
spint *  type,
spint *  sn,
double  tol,
double  gthresh 
)

Perform the analysis phase of sparse eigen-value factorization.

Parameters
[in]ApCSC format column pointer
[in]AiCSC format row index
[in]AxCSC format matrix nonzero entries
[in]dimDimension of the matrix
[out]iworkInteger working array for the analysis phase
[in]liworkLength of "iwork" or the expected length of integer working array
[out]workDouble working array for the analysis phase
[in]lworkLength of "lwork" or the expected length of double working array
[out]typeType of the matrix
[out]snSize of the submatrix
[in]tolTolerance to classify if a matrix is rank-one by $||A - a a^T||_F \leq tol$
[in]gthreshThreshold of (submatrix size / dim) classifying a matrix as general or sparse
Returns
retcode Status of the analysis phase

Perform the analysis phase of the sparse eigen-value factorization.

If all the necessary memories are allocated, on exit, "work" and "iwork" are filled by the intermediate information which can be used in the factorization phase; "type" is filled by one of the five types; "sn" is filled by size of the submatrix.

If "dim" is supplied and the rest of the working array is incomplete, "lwork" and "work" will be respectively filled by the expected length of the double and integer working arrays

◆ speigs_compute_submat()

static void speigs_compute_submat ( spint *  p,
spint *  i,
spint  n,
spint *  sn,
spint *  nnzs,
spint *  perm,
spint *  iperm 
)
static

Compute the dense submatrix of a large sparse matrix.

Parameters
[in]pCSC format column pointer
[in]iCSC format row index
[in]nDimension of the matrix
[out]snDimension of the submatrix
[in]nnzsNumber of nonzeros in each column
[out]permPermutation that gathers nonzero elements
[out]ipermInverse permutation

On exit, "perm" and "iperm" will be filled by the permutation and its inverse respectively

◆ speigs_factorize()

spint speigs_factorize ( spint *  Ap,
spint *  Ai,
double *  Ax,
spint *  dim,
spint *  aiwork,
double *  awork,
spint *  type,
spint *  sn,
spint *  iwork,
spint *  liwork,
double *  work,
spint *  lwork,
double *  evals,
double *  evecs,
spint *  rank,
double  tol 
)

Perform the analysis phase of sparse eigen-value factorization.

Parameters
[in]ApCSC format column pointer
[in]AiCSC format row index
[in]AxCSC format matrix nonzero entries
[in]dimDimension of the matrix
[in]aiworkInteger working array from the analysis phase
[in]aworkDouble working array from the analysis phase
[in]type"type" from the analysis phase
[in]sn"sn" from the analysis phase
[in]iworkInteger working array for the factorization phase
[in]liworkLength of "iwork" or the expected length of integer working array
[in]workDouble working array for the factorization phase
[in]lworkLength of "lwork" or the expected length of double working array
[out]evalsEigen-values after factorization
[out]evecsEigen-vectors after factorization
[out]rankRank of the factorized matrix
[in]tolTolerance to tell if an eigen-value is 0
Returns
retcode Status of the factorization phase

Perform the analysis phase of the sparse eigen-value factorization.

If all the necessary memories are allocated, on exit, "work" and "iwork" are filled by the intermediate information which can be used in the factorization phase; "type" is filled by one of the five types; "sn" is filled by size of the submatrix.

If "dim" is supplied and the rest of the working array is incomplete, "lwork" and "work" will be respectively filled by the expected length of the double and integer working arrays

◆ speigs_factorize_dense()

static spint speigs_factorize_dense ( double *  a,
double *  evals,
double *  evecs,
spint *  n,
spint *  liwork,
spint *  iwork,
spint *  lwork,
double *  work,
spint *  isuppz 
)
static

Compute the eigen factorization of a general full matrix.

Parameters
[in]aDense array that contains the matrix to factorize
[out]evalsEigen-values after factorization
[out]evecsEigen-vectors after factorization
[in]nDimension of the dense matrix
[in]liworkLength of the integer working array for Lapack
[in]iworkInteger working array for Lapack
[in]lworkLength of double working array for Lapack
[in]workDouble working array for Lapack
[in]isuppzAuxiliary placeholder for Lapack parameter
Returns
retcode Status of the factorization

On exit, "evals" and "evecs" will be overwritten by the eigen-decomposition of the matrix. "rank" is the rank of the matrix The routine is a wrapper of the Lapack dsyevr function

◆ speigs_factorize_diag()

static spint speigs_factorize_diag ( spint *  p,
spint *  i,
double *  x,
spint  n,
spint *  aiwork,
double *  awork,
spint *  sn,
spint *  iwork,
spint *  liwork,
double *  work,
spint *  lwork,
double *  evals,
double *  evecs,
spint *  rank,
double  tol 
)
static

Compute the eigen factorization of a diagonal matrix.

Parameters
[in]pCSC format column pointer
[in]iCSC format row index
[in]xCSC format matrix nonzero entries
[in]nDimension of the matrix
[in]aiworkInteger working array from the analysis phase
[in]aworkDouble working array from the analysis phase
[in]snDimension of the submatrix
[in]iworkInteger working array for the factorization phase
[in]liworkLength of "iwork"
[in]workDouble working array for the factorization phase
[in]lworkLength of "work"
[out]evalsEigen-values after factorization
[out]evecsEigen-vectors after factorization
[out]rankRank of the factorized matrix
[in]tolTolerance to tell if an eigen-value is 0
Returns
retcode Status of the factorization

On exit, "evals" and "evecs" will be overwritten by the eigen-decomposition of the matrix. "rank" is the rank of the matrix Since the matrix is diagonal, all the eigen-vectors are unit vectors and eigen-values are determined by the elements in "x"

◆ speigs_factorize_general()

static spint speigs_factorize_general ( spint *  p,
spint *  i,
double *  x,
spint  n,
spint *  aiwork,
double *  awork,
spint *  sn,
spint *  iwork,
spint *  liwork,
double *  work,
spint *  lwork,
double *  evals,
double *  evecs,
spint *  rank,
double  tol 
)
static

Compute the eigen factorization of a general dense matrix.

Parameters
[in]pCSC format column pointer
[in]iCSC format row index
[in]xCSC format matrix nonzero entries
[in]nDimension of the matrix
[in]aiworkInteger working array from the analysis phase
[in]aworkDouble working array from the analysis phase
[in]snDimension of the submatrix
[in]iworkInteger working array for the factorization phase
[in]liworkLength of "iwork"
[in]workDouble working array for the factorization phase
[in]lworkLength of "work"
[out]evalsEigen-values after factorization
[out]evecsEigen-vectors after factorization
[out]rankRank of the factorized matrix
[in]tolTolerance to tell if an eigen-value is 0
Returns
retcode Status of the factorization

On exit, "evals" and "evecs" will be overwritten by the eigen-decomposition of the matrix. "rank" is the rank of the matrix The routine converts the sparse matrix into a dense array and calls Lapack directly. Slow in general

◆ speigs_factorize_rankone()

static spint speigs_factorize_rankone ( spint *  p,
spint *  i,
double *  x,
spint  n,
spint *  aiwork,
double *  awork,
spint *  sn,
spint *  iwork,
spint *  liwork,
double *  work,
spint *  lwork,
double *  evals,
double *  evecs,
spint *  rank,
double  tol 
)
static

Compute the eigen factorization of a rank-one matrix.

Parameters
[in]pCSC format column pointer
[in]iCSC format row index
[in]xCSC format matrix nonzero entries
[in]nDimension of the matrix
[in]aiworkInteger working array from the analysis phase
[in]aworkDouble working array from the analysis phase
[in]snDimension of the submatrix
[in]iworkInteger working array for the factorization phase
[in]liworkLength of "iwork"
[in]workDouble working array for the factorization phase
[in]lworkLength of "work"
[out]evalsEigen-values after factorization
[out]evecsEigen-vectors after factorization
[out]rankRank of the factorized matrix
[in]tolTolerance to tell if an eigen-value is 0
Returns
retcode Status of the factorization

On exit, "evals" and "evecs" will be overwritten by the eigen-decomposition of the matrix. "rank" is the rank of the matrix Since the matrix is rank-one, the "awork" array from the analysis phase contains the eigen-decomposition

◆ speigs_factorize_sparse()

static spint speigs_factorize_sparse ( spint *  p,
spint *  i,
double *  x,
spint  n,
spint *  aiwork,
double *  awork,
spint *  sn,
spint *  iwork,
spint *  liwork,
double *  work,
spint *  lwork,
double *  evals,
double *  evecs,
spint *  rank,
double  tol 
)
static

Compute the eigen factorization of a sparse matrix admitting an easier submatrix representation.

Parameters
[in]pCSC format column pointer
[in]iCSC format row index
[in]xCSC format matrix nonzero entries
[in]nDimension of the matrix
[in]aiworkInteger working array from the analysis phase
[in]aworkDouble working array from the analysis phase
[in]snDimension of the submatrix
[in]iworkInteger working array for the factorization phase
[in]liworkLength of "iwork"
[in]workDouble working array for the factorization phase
[in]lworkLength of "work"
[out]evalsEigen-values after factorization
[out]evecsEigen-vectors after factorization
[out]rankRank of the factorized matrix
[in]tolTolerance to tell if an eigen-value is 0
Returns
retcode Status of the factorization

On exit, "evals" and "evecs" will be overwritten by the eigen-decomposition of the matrix. "rank" is the rank of the matrix The routine uses the permutation and inverse permutation information collected in the analysis phase to formulate the submatrix, factorizes the submatrix and finally recovers the decomposition using the inverse permutation

◆ speigs_factorize_two()

static spint speigs_factorize_two ( spint *  p,
spint *  i,
double *  x,
spint  n,
spint *  aiwork,
double *  awork,
spint *  sn,
spint *  iwork,
spint *  liwork,
double *  work,
spint *  lwork,
double *  evals,
double *  evecs,
spint *  rank,
double  tol 
)
static

Compute the eigen factorization of a two-two matrix.

Parameters
[in]pCSC format column pointer
[in]iCSC format row index
[in]xCSC format matrix nonzero entries
[in]nDimension of the matrix
[in]aiworkInteger working array from the analysis phase
[in]aworkDouble working array from the analysis phase
[in]snDimension of the submatrix
[in]iworkInteger working array for the factorization phase
[in]liworkLength of "iwork"
[in]workDouble working array for the factorization phase
[in]lworkLength of "work"
[out]evalsEigen-values after factorization
[out]evecsEigen-vectors after factorization
[out]rankRank of the factorized matrix
[in]tolTolerance to tell if an eigen-value is 0
Returns
retcode Status of the factorization

On exit, "evals" and "evecs" will be overwritten by the eigen-decomposition of the matrix. "rank" is the rank of the matrix Since the matrix composes of 2 by 2 submatrices, Givens' rotation is employed to factorize the matrixf

◆ speigs_factorize_zero()

static spint speigs_factorize_zero ( spint *  p,
spint *  i,
double *  x,
spint  n,
spint *  aiwork,
double *  awork,
spint *  sn,
spint *  iwork,
spint *  liwork,
double *  work,
spint *  lwork,
double *  evals,
double *  evecs,
spint *  rank,
double  tol 
)
static

Compute the eigen factorization of an all-zero matrix.

Parameters
[in]pCSC format column pointer
[in]iCSC format row index
[in]xCSC format matrix nonzero entries
[in]nDimension of the matrix
[in]aiworkInteger working array from the analysis phase
[in]aworkDouble working array from the analysis phase
[in]snDimension of the submatrix
[in]iworkInteger working array for the factorization phase
[in]liworkLength of "iwork"
[in]workDouble working array for the factorization phase
[in]lworkLength of "work"
[out]evalsEigen-values after factorization
[out]evecsEigen-vectors after factorization
[out]rankRank of the factorized matrix
[in]tolTolerance to tell if an eigen-value is 0
Returns
retcode Status of the factorization

On exit, "evals" and "evecs" will be overwritten by the eigen-decomposition of the matrix. "rank" is the rank of the matrix Since the matrix is all-zero, no operation is needed.

◆ speigs_is_diag()

static void speigs_is_diag ( spint *  p,
spint *  i,
spint  n,
spint *  is_diag 
)
static

Check if a matrix is diagonal.

Parameters
[in]pCSC format column pointer
[in]iCSC format row index
[in]nDimension of the matrix
[out]is_diagIs the matrix diagonal?

◆ speigs_is_rankone()

static void speigs_is_rankone ( spint *  p,
spint *  i,
double *  x,
spint  n,
spint *  is_rankone,
double *  work,
double  tol 
)
static

Find out if a matrix is rank-one. $ A = \alpha a a^T $.

Parameters
[in]pCSC format column pointer
[in]iCSC format row index
[in]xCSC format matrix nonzero entries
[in]nDimension of the matrix
[out]is_rankoneIs the matrix rank-one?
[out]workWorking array for rank-one detection
[in]tolTolerance for rank-one classification $||A - a a^T||_F \leq tol$

On exit, the array "work" would be filled by the rank-one factor a if A is rank-one

Variable Documentation

◆ speig_routines

spint(* speig_routines[6])(spint *, spint *, double *, spint, spint *, double *, spint *, spint *, spint *, double *, spint *, double *, double *, spint *, double) ( spint *  ,
spint *  ,
double *  ,
spint  ,
spint *  ,
double *  ,
spint *  ,
spint *  ,
spint *  ,
double *  ,
spint *  ,
double *  ,
double *  ,
spint *  ,
double   
)
static
Initial value:
=
{
&speigs_factorize_zero,
&speigs_factorize_sparse,
&speigs_factorize_general,
&speigs_factorize_rankone,
&speigs_factorize_diag,
&speigs_factorize_two
}
speigs_factorize_diag
static spint speigs_factorize_diag(spint *p, spint *i, double *x, spint n, spint *aiwork, double *awork, spint *sn, spint *iwork, spint *liwork, double *work, spint *lwork, double *evals, double *evecs, spint *rank, double tol)
Compute the eigen factorization of a diagonal matrix.
Definition: speigs.c:229
speigs_factorize_general
static spint speigs_factorize_general(spint *p, spint *i, double *x, spint n, spint *aiwork, double *awork, spint *sn, spint *iwork, spint *liwork, double *work, spint *lwork, double *evals, double *evecs, spint *rank, double tol)
Compute the eigen factorization of a general dense matrix.
Definition: speigs.c:444
speigs_factorize_sparse
static spint speigs_factorize_sparse(spint *p, spint *i, double *x, spint n, spint *aiwork, double *awork, spint *sn, spint *iwork, spint *liwork, double *work, spint *lwork, double *evals, double *evecs, spint *rank, double tol)
Compute the eigen factorization of a sparse matrix admitting an easier submatrix representation.
Definition: speigs.c:384
speigs_factorize_zero
static spint speigs_factorize_zero(spint *p, spint *i, double *x, spint n, spint *aiwork, double *awork, spint *sn, spint *iwork, spint *liwork, double *work, spint *lwork, double *evals, double *evecs, spint *rank, double tol)
Compute the eigen factorization of an all-zero matrix.
Definition: speigs.c:199
speigs_factorize_rankone
static spint speigs_factorize_rankone(spint *p, spint *i, double *x, spint n, spint *aiwork, double *awork, spint *sn, spint *iwork, spint *liwork, double *work, spint *lwork, double *evals, double *evecs, spint *rank, double tol)
Compute the eigen factorization of a rank-one matrix.
Definition: speigs.c:319
speigs_factorize_two
static spint speigs_factorize_two(spint *p, spint *i, double *x, spint n, spint *aiwork, double *awork, spint *sn, spint *iwork, spint *liwork, double *work, spint *lwork, double *evals, double *evecs, spint *rank, double tol)
Compute the eigen factorization of a two-two matrix.
Definition: speigs.c:268

The jump table for eigen routines.

Currently contains six implementations of eigen routines