| 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. . 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] | n | Dimension of the matrix
  [in] | sn | Dimension of the submatrix
  [in] | type | Type of the matrix
  [out] | liwork | Estimated integer workspace length
  [out] | lwork | Estimated 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] | Ap | CSC format column pointer
  [in] | Ai | CSC format row index
  [in] | Ax | CSC format matrix nonzero entries
  [in] | dim | Dimension of the matrix
  [out] | iwork | Integer working array for the analysis phase
  [in] | liwork | Length of "iwork" or the expected length of integer working array
  [out] | work | Double working array for the analysis phase
  [in] | lwork | Length of "lwork" or the expected length of double working array
  [out] | type | Type of the matrix
  [out] | sn | Size of the submatrix
  [in] | tol | Tolerance to classify if a matrix is rank-one by
  [in] | gthresh | Threshold 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] | p | CSC format column pointer
  [in] | i | CSC format row index
  [in] | n | Dimension of the matrix
  [out] | sn | Dimension of the submatrix
  [in] | nnzs | Number of nonzeros in each column
  [out] | perm | Permutation that gathers nonzero elements
  [out] | iperm | Inverse 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] | Ap | CSC format column pointer
  [in] | Ai | CSC format row index
  [in] | Ax | CSC format matrix nonzero entries
  [in] | dim | Dimension of the matrix
  [in] | aiwork | Integer working array from the analysis phase
  [in] | awork | Double working array from the analysis phase
  [in] | type | "type" from the analysis phase
  [in] | sn | "sn" from the analysis phase
  [in] | iwork | Integer working array for the factorization phase
  [in] | liwork | Length of "iwork" or the expected length of integer working array
  [in] | work | Double working array for the factorization phase
  [in] | lwork | Length of "lwork" or the expected length of double working array
  [out] | evals | Eigen-values after factorization
  [out] | evecs | Eigen-vectors after factorization
  [out] | rank | Rank of the factorized matrix
  [in] | tol | Tolerance 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] | a | Dense array that contains the matrix to factorize
  [out] | evals | Eigen-values after factorization
  [out] | evecs | Eigen-vectors after factorization
  [in] | n | Dimension of the dense matrix
  [in] | liwork | Length of the integer working array for Lapack
  [in] | iwork | Integer working array for Lapack
  [in] | lwork | Length of double working array for Lapack
  [in] | work | Double working array for Lapack
  [in] | isuppz | Auxiliary 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] | p | CSC format column pointer
  [in] | i | CSC format row index
  [in] | x | CSC format matrix nonzero entries
  [in] | n | Dimension of the matrix
  [in] | aiwork | Integer working array from the analysis phase
  [in] | awork | Double working array from the analysis phase
  [in] | sn | Dimension of the submatrix
  [in] | iwork | Integer working array for the factorization phase
  [in] | liwork | Length of "iwork"
  [in] | work | Double working array for the factorization phase
  [in] | lwork | Length of "work"
  [out] | evals | Eigen-values after factorization
  [out] | evecs | Eigen-vectors after factorization
  [out] | rank | Rank of the factorized matrix
  [in] | tol | Tolerance 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] | p | CSC format column pointer
  [in] | i | CSC format row index
  [in] | x | CSC format matrix nonzero entries
  [in] | n | Dimension of the matrix
  [in] | aiwork | Integer working array from the analysis phase
  [in] | awork | Double working array from the analysis phase
  [in] | sn | Dimension of the submatrix
  [in] | iwork | Integer working array for the factorization phase
  [in] | liwork | Length of "iwork"
  [in] | work | Double working array for the factorization phase
  [in] | lwork | Length of "work"
  [out] | evals | Eigen-values after factorization
  [out] | evecs | Eigen-vectors after factorization
  [out] | rank | Rank of the factorized matrix
  [in] | tol | Tolerance 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] | p | CSC format column pointer
  [in] | i | CSC format row index
  [in] | x | CSC format matrix nonzero entries
  [in] | n | Dimension of the matrix
  [in] | aiwork | Integer working array from the analysis phase
  [in] | awork | Double working array from the analysis phase
  [in] | sn | Dimension of the submatrix
  [in] | iwork | Integer working array for the factorization phase
  [in] | liwork | Length of "iwork"
  [in] | work | Double working array for the factorization phase
  [in] | lwork | Length of "work"
  [out] | evals | Eigen-values after factorization
  [out] | evecs | Eigen-vectors after factorization
  [out] | rank | Rank of the factorized matrix
  [in] | tol | Tolerance 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] | p | CSC format column pointer
  [in] | i | CSC format row index
  [in] | x | CSC format matrix nonzero entries
  [in] | n | Dimension of the matrix
  [in] | aiwork | Integer working array from the analysis phase
  [in] | awork | Double working array from the analysis phase
  [in] | sn | Dimension of the submatrix
  [in] | iwork | Integer working array for the factorization phase
  [in] | liwork | Length of "iwork"
  [in] | work | Double working array for the factorization phase
  [in] | lwork | Length of "work"
  [out] | evals | Eigen-values after factorization
  [out] | evecs | Eigen-vectors after factorization
  [out] | rank | Rank of the factorized matrix
  [in] | tol | Tolerance 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] | p | CSC format column pointer
  [in] | i | CSC format row index
  [in] | x | CSC format matrix nonzero entries
  [in] | n | Dimension of the matrix
  [in] | aiwork | Integer working array from the analysis phase
  [in] | awork | Double working array from the analysis phase
  [in] | sn | Dimension of the submatrix
  [in] | iwork | Integer working array for the factorization phase
  [in] | liwork | Length of "iwork"
  [in] | work | Double working array for the factorization phase
  [in] | lwork | Length of "work"
  [out] | evals | Eigen-values after factorization
  [out] | evecs | Eigen-vectors after factorization
  [out] | rank | Rank of the factorized matrix
  [in] | tol | Tolerance 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] | p | CSC format column pointer
  [in] | i | CSC format row index
  [in] | x | CSC format matrix nonzero entries
  [in] | n | Dimension of the matrix
  [in] | aiwork | Integer working array from the analysis phase
  [in] | awork | Double working array from the analysis phase
  [in] | sn | Dimension of the submatrix
  [in] | iwork | Integer working array for the factorization phase
  [in] | liwork | Length of "iwork"
  [in] | work | Double working array for the factorization phase
  [in] | lwork | Length of "work"
  [out] | evals | Eigen-values after factorization
  [out] | evecs | Eigen-vectors after factorization
  [out] | rank | Rank of the factorized matrix
  [in] | tol | Tolerance 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] | p | CSC format column pointer
  [in] | i | CSC format row index
  [in] | n | Dimension of the matrix
  [out] | is_diag | Is 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. .

Parameters

  [in] | p | CSC format column pointer
  [in] | i | CSC format row index
  [in] | x | CSC format matrix nonzero entries
  [in] | n | Dimension of the matrix
  [out] | is_rankone | Is the matrix rank-one?
  [out] | work | Working array for rank-one detection
  [in] | tol | Tolerance for rank-one classification

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