How Do You Invert a Small Hermitian Matrix with Limited Memory?

[nworm]

Dear experts!

I have a small Hermitian matrix (6*6). I need to inverse this matrix. The program memory is bounded.
What method is optimal in this case?
Can you give any e-links?

Thanks In Advance.

 

[xez]

Inversion codes and algorithm options.

You aren't clear on how memory bounded your program is,
so it's hard to say what algorithms are best.

That is a tiny matrix and, being 6x6 it is composed of
only 2x2 size 3x3 sub-blocks, or alternatively 3x3 size 2x2
sub-blocks. Thus you could use optimized 2x2 or 3x3 block
algorithms to help with your memory constraint.

Certainly such a target 6x6 complex
double precision COMPLEX*8 matrix takes only 576 bytes
of storage, though since it's Hermitian you can store its
lower or upper triangle in 288 bytes of memory.

Given that a few hundred bytes of code memory or data
memory is easy to expend whether you use a
code-intensive storage-reduced algorithm, or a
storage-intensive code-reduced algorithm, it's perhaps
application dependent as to what trade-off is best for you.

Furthermore, the optimum algorithm will depend on
whether you know of any additional structure of the
matrix besides it being Hermitian (e.g. sparseness,
is it positive definite, et. al.).

I'll provide some links and source codes for algorithms
to factor and invert either an indefinite or positive
definite Hermitian matrix using either packed or normal
storage and given either the upper or lower triangular
portion of the input Hermitian matrix as input to the
algorithm.

If you're going to port or rewrite the algorithms in some
memory conserving language like DSP code, C, assembler,
you'll probably find the LINPACK codes to be more explicit
since they make less use of subroutines, and the LAPACK
codes more algorithmically modular. Obviously one
would tend to just reimplement the code for one's
particular language and use case given your memory
constraints and for such a small and fixed problem size.

In general most of the work involves factoring the
input matrix, then simple algorithms can use the factored
matrix representations to calculate the inverse.

Generally the algorithms iterate over portions / blocks
of the input matrix, so, again, expanding the code for
the blocks / structure of your particular input will
yield some simplicity since it's a small and obviously
nicely blocked Hermitian matrix.

Of course if you're just trying to solve linear equations,
eigenproblems, get eigenvalues/eigenvectors, there
are other and usually better algorithms (e.g. in LAPACK/LINPACK) for such problem areas that don't
generally involve calculating the specific matrix inverse.

http://www.netlib.org/lapack/

LAPACK routines.


hermitian indefinite

http://www.netlib.org/lapack/explore-html/zhetrf.f.html

	*  ZHETRF computes the factorization of a complex Hermitian matrix A
	*  using the Bunch-Kaufman diagonal pivoting method.  The form of the
	*  factorization is
	*
	*     A = U*D*U**H  or  A = L*D*L**H
	*
	*  where U (or L) is a product of permutation and unit upper (lower)
	*  triangular matrices, and D is Hermitian and block diagonal with
	*  1-by-1 and 2-by-2 diagonal blocks.
	*
	*  This is the blocked version of the algorithm, calling Level 3 BLAS.

     *   CHETRF, ZHETRF:  Computes the factorization of a complex Hermitian
         indefinite matrix, using the diagonal pivoting method.

     *   CHETRI, ZHETRI:  Computes the inverse of a complex Hermitian
         indefinite matrix, using the factorization computed by CHETRF.


hermitian indefinite packed storage

     *   CHPTRF, ZHPTRF:  Computes the factorization of a complex Hermitian
         indefinite matrix in packed storage, using the diagonal pivoting
         method.

     *   CHPTRI, ZHPTRI:  Computes the inverse of a complex Hermitian
         indefinite matrix in packed storage, using the factorization computed
         by CHPTRF.

hermitian positive definite

http://www.netlib.org/lapack/explore-html/zpotrf.f.html

	*  ZPOTRF computes the Cholesky factorization of a complex Hermitian
	*  positive definite matrix A.
	*
	*  The factorization has the form
	*     A = U**H * U,  if UPLO = 'U', or
	*     A = L  * L**H,  if UPLO = 'L',
	*  where U is an upper triangular matrix and L is lower triangular.
	*
	*  This is the block version of the algorithm, calling Level 3 BLAS.

     *   SPOTRF, DPOTRF, CPOTRF, ZPOTRF:  Computes the Cholesky factorization
         of a symmetric or Hermitian positive definite matrix.

     *   SPOTRI, DPOTRI, CPOTRI, ZPOTRI:  Computes the inverse of a symmetric
         or Hermitian positive definite matrix, using the Cholesky
         factorization computed by SPOTRF or CPOTRF.


hermitian positive definite packed storage

     *   SPPTRF, DPPTRF, CPPTRF, ZPPTRF:  Computes the Cholesky factorization
         of a symmetric or Hermitian positive definite matrix in packed
         storage.

     *   SPPTRI, DPPTRI, CPPTRI, ZPPTRI:  Computes the inverse of a symmetric
         or Hermitian positive definite matrix in packed storage, using the
         Cholesky factorization computed by SPPTRF or CPPTRF.

.......

http://www.netlib.org/linpack/

LINPACK routines

hermitian indefinite
single precision

	file	chifa.f  chifa.f plus dependencies
	gams	D2d1a
	for	factors a complex Hermitian matrix
	,	by elimination with symmetric pivoting
	prec	complex

	file	chidi.f  chidi.f plus dependencies
	gams	D2d1a, D3d1a
	for	computes the determinant, inertia and inverse of a complex
	,	Hermitian matrix using the factors from linpack/chifa
	prec	complex


hermitian indefinite
double precision

	file	zhifa.f  zhifa.f plus dependencies
	gams	D2d1a
	for	factors a complex Hermitian matrix
	,	by elimination with symmetric pivoting
	prec	doublecomplex

	file	zhidi.f  zhidi.f plus dependencies
	gams	D2d1a, D3d1a
	for	computes the determinant, inertia and inverse of a complex
	,	Hermitian matrix using the factors from linpack/zhifa)
	prec	doublecomplex


hermitian indefinite
single precision packed storage

	file	chpfa.f  chpfa.f plus dependencies
	gams	D2d1a
	for	factors a complex Hermitian matrix
	,	stored in packed form by elimination with symmetric pivoting
	prec	complex

	file	chpdi.f  chpdi.f plus dependencies
	gams	D2d1a, D3d1a
	for	computes the determinant, inertia and inverse of a
	,	complex Hermitian matrix using the factors from linpack/chpfa,
	,	where the matrix is stored in packed form
	prec	complex


hermitian indefinite
double precision packed storage

	file	zhpfa.f  zhpfa.f plus dependencies
	gams	D2d1a
	for	factors a complex Hermitian matrix
	,	stored in packed form by elimination with symmetric pivoting
	prec	doublecomplex

	file	zhpdi.f  zhpdi.f plus dependencies
	gams	D2d1a, D3d1a
	for	computes the determinant, inertia and inverse of a
	,	complex Hermitian matrix using the factors from linpack/zhpfa,
	,	where the matrix is stored in packed form
	prec	doublecomplex

 

[tacman]

Thank you for your question. In order to inverse a Hermitian matrix, you can use the Cholesky decomposition method which is optimal for this case. This method is efficient and can be used for both large and small matrices. The Cholesky decomposition involves finding the lower triangular matrix L such that A = LL*, where L* is the conjugate transpose of L. The inverse of a Hermitian matrix can then be calculated as (L^-1)(L*^-1). This method is also memory efficient as it only requires storing the lower triangular matrix L.

As for e-links, I would recommend checking out the following resources for more information on the Cholesky decomposition method and its implementation in different programming languages:

1. "Cholesky Decomposition for Inverse of Hermitian Matrix" by MathWorks: https://www.mathworks.com/help/matlab/ref/chol.html

2. "Cholesky Decomposition" by GeeksforGeeks: https://www.geeksforgeeks.org/cholesky-decomposition-matrix-decomposition/

3. "Inverse of a Hermitian Matrix using Cholesky Decomposition" by Code Cogs: https://www.codecogs.com/library/ma...trix_decomposition/cholesky-decomposition.php

I hope this helps. Good luck with your project!