Report · 2009 · Open access

A Fast Parallel Algorithm for Selected Inversion of Structured Sparse Matrices with Application to 2D Electronic Structure Calculations

Lin Lin, Chao Yang, Jiangfeng Lu, Lexing Ying, E Weinan

OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · Published 25 September 2009 · DOI 10.2172/974182

Free PDFView at the publisherCite this paper

In brief

“A Fast Parallel Algorithm for Selected Inversion of Structured Sparse Matrices with Application to 2D Electronic Structure Calculations” is a 2009 report by Lin Lin and 4 co-authors, published in OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information). OpenAlex counts 3 citations as of 16 November 2026. It is open access: the full text is free to read at OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information).

Citations
3
Authors
5

Abstract

We present an efficient parallel algorithm and its implementation for computing the diagonal of $H^-1$ where $H$ is a 2D Kohn-Sham Hamiltonian discretized on a rectangular domain using a standard second order finite difference scheme. This type of calculation can be used to obtain an accurate approximation to the diagonal of a Fermi-Dirac function of $H$ through a recently developed pole-expansion technique \cite{LinLuYingE2009}. The diagonal elements are needed in electronic structure calculations for quantum mechanical systems \citeHohenbergKohn1964, KohnSham 1965,DreizlerGross1990. We show how elimination tree is used to organize the parallel computation and how synchronization overhead is reduced by passing data level by level along this tree using the technique of local buffers and relative indices. We analyze the performance of our implementation by examining its load balance and communication overhead. We show that our implementation exhibits an excellent weak scaling on a large-scale high performance distributed parallel machine. When compared with standard approach for evaluating the diagonal a Fermi-Dirac function of a Kohn-Sham Hamiltonian associated a 2D electron quantum dot, the new pole-expansion technique that uses our algorithm to compute the diagonal of $(H-z_i I)^-1$ for a small number of poles $z_i$ is much faster, especially when the quantum dot contains many electrons.

Cite this paper

Formatted from the catalogue record. Check names, capitals and page numbers against the paper before you submit.

APA 7

Lin, L., Yang, C., Lu, J., Ying, L., & Weinan, E. (2009). A Fast Parallel Algorithm for Selected Inversion of Structured Sparse Matrices with Application to 2D Electronic Structure Calculations. OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information). https://doi.org/10.2172/974182

MLA 9

Lin, Lin, et al. “A Fast Parallel Algorithm for Selected Inversion of Structured Sparse Matrices with Application to 2D Electronic Structure Calculations.” OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information), 2009. https://doi.org/10.2172/974182.

Chicago

Lin, Lin, Chao Yang, Jiangfeng Lu, Lexing Ying, and E Weinan. 2009. “A Fast Parallel Algorithm for Selected Inversion of Structured Sparse Matrices with Application to 2D Electronic Structure Calculations.” OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information). https://doi.org/10.2172/974182.

Harvard

Lin, L. et al. (2009) ‘A Fast Parallel Algorithm for Selected Inversion of Structured Sparse Matrices with Application to 2D Electronic Structure Calculations’, OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information). doi:10.2172/974182.

IEEE

L. Lin, C. Yang, J. Lu, L. Ying, and E. Weinan, “A Fast Parallel Algorithm for Selected Inversion of Structured Sparse Matrices with Application to 2D Electronic Structure Calculations,” OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information), 2009, doi: 10.2172/974182.

BibTeX

@article{lin2009fast,
  title     = {{A Fast Parallel Algorithm for Selected Inversion of Structured Sparse Matrices with Application to 2D Electronic Structure Calculations}},
  author    = {Lin, Lin and Yang, Chao and Lu, Jiangfeng and Ying, Lexing and Weinan, E},
  journal   = {OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information)},
  year      = {2009},
  doi       = {10.2172/974182},
  url       = {https://doi.org/10.2172/974182}
}

Download for a reference manager: BibTeX (.bib) · RIS for Zotero, Mendeley and EndNote (.ris)

Topic and keywords

Physical Sciences › Computer Science › Computational Theory and Mathematics › Matrix Theory and Algorithms

  • parallel algorithms
  • Kohn-Sham Hamiltonian
  • electronic structure calculations
  • Fermi-Dirac distribution
  • elimination tree
  • quantum dots
  • load balancing
  • communication overhead

Work with this paper

Most-cited papers in Computer Science

All highly cited Computer Science papers

Questions about this paper

How do I cite this paper in APA style?

Lin, L., Yang, C., Lu, J., Ying, L., & Weinan, E. (2009). A Fast Parallel Algorithm for Selected Inversion of Structured Sparse Matrices with Application to 2D Electronic Structure Calculations. OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information). https://doi.org/10.2172/974182

How many times has this paper been cited?

3 times, according to OpenAlex on 16 November 2026. Google Scholar and Scopus count different sets of sources, so their numbers differ.

Is this paper free to read?

Yes. It is open access: read the free full text at OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information).

Who wrote this paper?

Lin Lin, Chao Yang, Jiangfeng Lu, Lexing Ying, E Weinan.

What is the DOI of this paper?

10.2172/974182. The permanent link is https://doi.org/10.2172/974182.

Bibliographic data from OpenAlex (CC0), last checked 16 November 2026. ResearchGuru does not host this paper; the links go to the publisher or the repository that does.