Scribd
Upload
47 views2 pages

Selected Inversion Summary

Selected inversion is a numerical method for efficiently computing specific entries of the inverse of a sparse matrix, focusing on non-zero elements to save time and memory. It is particularly useful in applications such as quantum simulations and circuit analysis, employing recursive algorithms based on elimination trees. The method has a lower computational complexity compared to full inverses and is supported by various software tools.

Uploaded by

taha23akter
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
47 views2 pages

Selected Inversion Summary

Selected inversion is a numerical method for efficiently computing specific entries of the inverse of a sparse matrix, focusing on non-zero elements to save time and memory. It is particularly useful in applications such as quantum simulations and circuit analysis, employing recursive algorithms based on elimination trees. The method has a lower computational complexity compared to full inverses and is supported by various software tools.

Uploaded by

taha23akter
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Selected Inversion: Computing Sparse Inverse Efficiently

Selected Inversion: Computing Selected Entries of A Efficiently

Definition:

Selected inversion is a numerical method used to compute only selected elements of the inverse of

a sparse matrix A, typically those corresponding to non-zero entries in A.

Why Use It:

- Full inverse A is dense, expensive to compute and store.

- Selected inversion targets only necessary entries, saving time and memory.

- Often needed in applications like quantum simulations, circuit analysis, FEM.

Mathematical Idea:

Given A = LDL (for symmetric A), or A = LU (general case), selected inversion uses recursive

algorithms based on elimination trees to compute:

(A) for specific (i, j), especially when A 0

Example:

For A = [[10, 0, 0], [3, 9, 0], [0, 7, 8]], we may only need:

(A), (A), (A)

This is common in quantum mechanics where Tr(A) is used.

Applications:

- Diagonal entries in Greens function (quantum physics)

- Impedance matrix entries (circuit simulation)


- Subdomain responses in FEM/BEM

- Graph-based metrics (commute time, effective resistance)

Algorithm Outline (Symmetric Case):

1. Perform Cholesky: A = LDL

2. Traverse elimination tree

3. Recursively compute only required entries using:

(A) = L D L, but selectively

Complexity:

- Much lower than full inverse.

- Near-linear for banded or nested-dissection-ordered matrices.

Software:

- symPACK (C++), selinv (Fortran), JANUS (MATLAB/Julia), custom Julia tools

Research Role:

- Supports approximate solvers with low-rank corrections

- Integrates with preconditioners (e.g., ILU+SelInv hybrids)

- Enables trace estimation and fast eigenvalue filtering

References:

- Lin, L., Lu, J., & Ying, L. (2011). Fast algorithm for selected inversion of structured sparse

matrices.

- Bollhfer, M., Saad, Y. (2006). Multilevel ILU for heterogeneous systems.

- Benzi, M., Tuma, M. (1999). Sparse approximate inverse preconditioner.

You might also like