Extension and optimization of the FIND algorithm: Computing Green's and less-than Green's functions
From MaRDI portal
Publication:422929
DOI10.1016/J.JCP.2011.05.027zbMATH Open1239.65027arXiv1104.0623OpenAlexW2169657480MaRDI QIDQ422929FDOQ422929
Authors: S. Li, Eric Darve 
Publication date: 18 May 2012
Published in: Journal of Computational Physics (Search for Journal in Brave)
Abstract: The FIND algorithm is a fast algorithm designed to calculate certain entries of the inverse of a sparse matrix. Such calculation is critical in many applications, e.g., quantum transport in nano-devices. We extended the algorithm to other matrix inverse related calculations. Those are required for example to calculate the less-than Green's function and the current density through the device. For a 2D device discretized as an N_x x N_y mesh, the best known algorithms have a running time of O(N_x^3 N_y), whereas FIND only requires O(N_x^2 N_y). Even though this complexity has been reduced by an order of magnitude, the matrix inverse calculation is still the most time consuming part in the simulation of transport problems. We could not reduce the order of complexity, but we were able to significantly reduce the constant factor involved in the computation cost. By exploiting the sparsity and symmetry, the size of the problem beyond which FIND is faster than other methods typically decreases from a 130x130 2D mesh down to a 40x40 mesh. These improvements make the optimized FIND algorithm even more competitive for real-life applications.
Full work available at URL: https://arxiv.org/abs/1104.0623
Recommendations
- Computing entries of the inverse of a sparse matrix using the FIND algorithm
- A fast algorithm for sparse matrix computations related to inversion
- Finding off-diagonal entries of the inverse of a large symmetric sparse matrix
- Fast algorithm for extracting the diagonal of the inverse matrix with application to the electronic structure analysis of metallic systems
- A Fast Parallel Algorithm for Selected Inversion of Structured Sparse Matrices with Application to 2D Electronic Structure Calculations
Gaussian eliminationnumerical examplessparse matrixGreen's functionfinite difference methodinverse matrixquantum transportnested dissectionrecursive Green's function methodtransport problemsFIND algorithmnanotransistor
Cites Work
- Title not available (Why is that?)
- A sparse matrix arithmetic based on \({\mathfrak H}\)-matrices. I: Introduction to \({\mathfrak H}\)-matrices
- SelInv---An Algorithm for Selected Inversion of a Sparse Symmetric Matrix
- A Fast $ULV$ Decomposition Solver for Hierarchically Semiseparable Representations
- Nested Dissection of a Regular Finite Element Mesh
- On computing certain elements of the inverse of a sparse matrix
- Direct Methods for Solving Symmetric Indefinite Systems of Linear Equations
- Partitioning Sparse Matrices with Eigenvectors of Graphs
- Some Stable Methods for Calculating Inertia and Solving Symmetric Linear Systems
- Some Fast Algorithms for Sequentially Semiseparable Representations
- Parallel Algorithms for Sparse Linear Systems
- Fast algorithm for extracting the diagonal of the inverse matrix with application to the electronic structure analysis of metallic systems
- A Fast Solver for HSS Representations via Sparse Matrices
- A parallel graph partitioning algorithm for a message-passing multiprocessor
- On Row and Column Orderings for Sparse Least Squares Problems
- A hybrid method for the parallel computation of Green's functions
- Computing entries of the inverse of a sparse matrix using the FIND algorithm
- General highly accurate algebraic coarsening
- Block tridiagonal matrix inversion and fast transmission calculations
Cited In (7)
- A fast algorithm for sparse matrix computations related to inversion
- Computing entries of the inverse of a sparse matrix using the FIND algorithm
- An approximate framework for quantum transport calculation with model order reduction
- A nested dissection approach to modeling transport in nanodevices: algorithms and applications
- Quantum machine learning: a classical perspective
- Fast sparse selected inversion
- Scalable atomistic simulations of quantum electron transport using empirical pseudopotentials
Uses Software
This page was built for publication: Extension and optimization of the FIND algorithm: Computing Green's and less-than Green's functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q422929)
