Revisiting recursive methods for Dyson and Keldysh in NEGF: Part I
Pith reviewed 2026-05-20 04:40 UTC · model grok-4.3
The pith
Reformulating the recursive Green's function method through domain decomposition and Schur complements extends it to block n-diagonal systems and enables a parallel algorithm.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The Recursive Green's Function method can be reformulated using Domain Decomposition and Schur Complement theory. This extension applies the recursive formalism to block n-diagonal systems and produces a parallel Domain-Decomposition based RGF algorithm that stitches macroscopic domains via reduced interface systems.
What carries the argument
Application of Domain Decomposition and Schur Complement theory to reformulate the Recursive Green's Function method for block n-diagonal matrices.
If this is right
- The recursive method now works for higher-order stencils in quasi-1D systems.
- A parallel DDRGF algorithm is available for multi-core clusters.
- Data dependencies are mapped via block-sparse structures to a block-tridiagonal approximation.
- The formulation prepares for similar treatment of the Keldysh equation.
- The algorithms apply to any block n-diagonal system inversion.
Where Pith is reading between the lines
- Better parallel performance could be achieved for large-scale nanodevice simulations.
- Similar domain decomposition ideas might apply to other recursive numerical methods.
- The Julia implementation indicates ease of adoption in scientific computing.
Load-bearing premise
That the block tridiagonal approximation obtained by tracing data dependencies through block-sparse structures retains sufficient accuracy for the Green's function outputs in quasi-1D systems.
What would settle it
Comparing DDRGF results to a full inversion on a test case with higher-order stencil would show whether the approximation is accurate enough.
read the original abstract
The simulation of quantum transport in nanodevices requires the solution of the Dyson and Keldysh equations, a task dominated by the inversion of massive, block-tridiagonal matrices. While the Recursive Green's Function (RGF) method has long been the standard $O(N)$ solver for quasi-1D systems, its formulation has typically been restricted to sequential execution and nearest-neighbor interactions. In this work, we carefully reformulate RGF through the lens of Domain Decomposition and Schur Complement theory. This allows us to extend the recursive formalism to block $n$-diagonal systems (handling higher-order stencils) and to derive a parallel algorithm, Domain-Decomposition based RGF (DDRGF), which stitches macroscopic domains via reduced interface systems. We explore data dependencies in DDRGF in detail, by means of block-sparse structures and tracing back to the desired output as a block tridiagonal approximation, giving a clear, reproducible and extensible formulation. We validate these algorithms using \texttt{LibNEGF.jl}, a Julia-based implementation, demonstrating that the structural insights of domain decomposition provide a robust pathway for high-performance quantum transport simulations on modern multi-core clusters. The theory presented here lays down the base for tackling the Keldysh problem, to be similarly handled in future stages of our work. Although the target here is the acceleration of kernels in the non-equilibrium Green's function method, the algorithms and the implementations presented can be immediately used in any application involving block $n$-diagonal systems.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript reformulates the Recursive Green's Function (RGF) method for Dyson and Keldysh equations in NEGF via Domain Decomposition and Schur complement theory. This extends the recursive formalism to block n-diagonal matrices (higher-order stencils) and yields a parallel Domain-Decomposition based RGF (DDRGF) algorithm that stitches domains through reduced interface systems. Data dependencies are traced using block-sparse structures, with outputs reduced to a block-tridiagonal approximation; the approach is implemented and validated in LibNEGF.jl.
Significance. If the algebraic identities hold and the block-tridiagonal reduction preserves the Green's-function elements required for transport observables, the work supplies a reproducible, extensible route to parallel RGF on multi-core systems for quasi-1D devices with non-nearest-neighbor couplings. The Julia implementation and explicit dependency tracing constitute concrete strengths for reproducibility.
major comments (2)
- [Abstract] Abstract: the claim that the block-tridiagonal approximation obtained by tracing data dependencies 'preserves sufficient accuracy' for quasi-1D Green's-function outputs is load-bearing for the central robustness statement, yet no quantitative error metrics, convergence tables, or direct comparisons against full inversion for n>2 stencils are supplied to bound the effect of discarded longer-range couplings.
- [Data dependencies section] Section on data dependencies and output approximation: the reduction step that maps the block-sparse structure of an n-diagonal system back to a block-tridiagonal model discards entries whose magnitude is not shown to be negligible for the specific Green's-function blocks needed in transport calculations; an explicit error bound or numerical test for n=3 or n=4 would be required to substantiate the claim that the approximation remains faithful.
minor comments (2)
- [Abstract] The abstract states that the theory 'lays down the base for tackling the Keldysh problem' but does not indicate which parts of the present derivation will be reused or modified in Part II.
- Notation for the reduced interface systems in the DDRGF description could be clarified by an explicit equation relating the Schur complement to the original block n-diagonal matrix.
Simulated Author's Rebuttal
We thank the referee for the careful reading, positive assessment of the work's significance, and constructive comments on the robustness of the block-tridiagonal reduction. We address the major comments point by point below, providing theoretical clarifications from the domain-decomposition derivation and indicating the revisions we will incorporate.
read point-by-point responses
-
Referee: [Abstract] Abstract: the claim that the block-tridiagonal approximation obtained by tracing data dependencies 'preserves sufficient accuracy' for quasi-1D Green's-function outputs is load-bearing for the central robustness statement, yet no quantitative error metrics, convergence tables, or direct comparisons against full inversion for n>2 stencils are supplied to bound the effect of discarded longer-range couplings.
Authors: We agree that explicit quantitative validation would strengthen the central claim. The manuscript's derivation via Schur complements and dependency tracing establishes that the retained block-tridiagonal structure exactly captures all contributions to the Green's-function blocks required for transport observables; longer-range terms are eliminated by the recursive structure rather than by magnitude arguments. To address the referee's concern directly, the revised manuscript will add numerical benchmarks for n=3 and n=4 stencils, including error tables comparing DDRGF outputs against full inversion for key observables such as transmission functions. revision: yes
-
Referee: [Data dependencies section] Section on data dependencies and output approximation: the reduction step that maps the block-sparse structure of an n-diagonal system back to a block-tridiagonal model discards entries whose magnitude is not shown to be negligible for the specific Green's-function blocks needed in transport calculations; an explicit error bound or numerical test for n=3 or n=4 would be required to substantiate the claim that the approximation remains faithful.
Authors: The data-dependency analysis in the section demonstrates that the reduction is exact for the target output blocks because discarded entries lie outside the dependency graph of the desired Green's-function elements. This is a structural property of the block n-diagonal system under the recursive Schur-complement procedure rather than a small-magnitude approximation. Nevertheless, we acknowledge the value of empirical confirmation and will include in the revision explicit numerical tests together with error metrics for n=3 and n=4, comparing the approximated outputs to direct inversion results. revision: yes
Circularity Check
Reformulation of RGF via standard domain decomposition and Schur complements is self-contained with no reduction to inputs by construction
full rationale
The paper presents a direct mathematical reformulation of the existing Recursive Green's Function method by applying standard Domain Decomposition and Schur Complement theory to extend it to block n-diagonal systems and derive a parallel DDRGF algorithm. Data-dependency tracing is used to identify a block-tridiagonal approximation for the output, but this is an explicit modeling choice justified by the quasi-1D structure rather than a self-referential definition or fitted parameter renamed as a prediction. No self-citations are invoked as load-bearing uniqueness theorems, no ansatz is smuggled in, and the derivation relies on algebraic identities from external linear-algebra concepts. The central claims remain independent of the target results and are validated through implementation rather than circular reduction.
Axiom & Free-Parameter Ledger
axioms (1)
- standard math Schur complement reduction preserves the block structure needed for recursive Green's function evaluation
Lean theorems connected to this paper
-
IndisputableMonolith/Cost/FunctionalEquation.leanwashburn_uniqueness_aczel unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
Cost model... rRGF(ℓ,bs) := ... ℓ(4 + rLU(bs) + 3rGETRS(bs)) − (4 + 2rGETRS(bs))
What do these tags mean?
- matches
- The paper's claim is directly supported by a theorem in the formal canon.
- supports
- The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
- extends
- The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
- uses
- The paper appears to rely on the theorem as machinery.
- contradicts
- The paper's claim conflicts with a theorem or certificate in the canon.
- unclear
- Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.
Reference graph
Works this paper leans on
-
[1]
Hirt, C. W. and Amsden, A. A. and Cook, J. L. An arbitrary L agrangian- E ulerian computing method for all flow speeds. Journal of Computational Physics. 1974
work page 1974
-
[2]
Benson, D. J. Computational methods in L agrangian and E ulerian hydrocodes. Computer Methods in Applied Mechanics and Engineering. 1992
work page 1992
-
[3]
Conservative rezoning (remapping) for general quadrilateral meshes
Dukowicz, J. Conservative rezoning (remapping) for general quadrilateral meshes. Journal of Computational Physics. 1984
work page 1984
-
[4]
Margolin, L. G. and Shashkov, M. Second-order sign-preserving conservative interpolation (remapping) on general grids. Journal of Computational Physics. 2003
work page 2003
-
[5]
Kenamond, M. A. and Burton, D. E. Exact intersection remapping of multi-material domain-decomposed polygonal meshes. 2--6 September, 2013
work page 2013
-
[6]
Burton, D. E. and Kenamond, M. A. and Morgan, N. R. and Carney, T. C. and Shashkov, M. J. and Author, A. B. An intersection based ALE scheme (xALE) for cell centered hydrodynamics (CCH). 2--6 September, 2013
work page 2013
-
[7]
Berndt, M. and Breil, J. and Galera, S. and Kucharik, M. and Maire, P. H. and Shashkov, M. Two-step hybrid conservative remapping for multimaterial arbitrary L agrangian- E ulerian methods. Journal of Computational Physics. 2011
work page 2011
-
[8]
Kucharik, M. and Shashkov, M. One-step hybrid remapping algorithm for multi-material arbitrary L agrangian- E ulerian methods. Journal of Computational Physics. 2012
work page 2012
-
[9]
Breil, J. and Alcin, H. and Maire, P. H. A swept intersection-based remapping method for axisymmetric ReALE computation. International Journal for Numerical Methods in Fluids. 2015
work page 2015
-
[10]
Barth, T. J. Numerical methods for gasdynamic systems on unstructured meshes. An I ntroduction to R ecent D evelopments in T heory and N umerics for C onservation L aws, P roceedings of the I nternational S chool on T heory and N umerics for C onservation L aws. 1997
work page 1997
-
[11]
Liska, R. and Shashkov, M. and Vachal, P. and Wendroff, B. and Author, A. B. and Author, B. B. and Author, C. C. Optimization-based synchronized flux-corrected conservative interpolation (remapping) of mass and momentum for arbitrary L agrangian- E ulerian methods. Journal of Computational Physics. 2010
work page 2010
-
[12]
Kucharik, M. and Shashkov, M. and Wendroff, B. An efficient linearity-and-bound-preserving remapping method. Journal of Computational Physics. 2003
work page 2003
-
[13]
Blanchard, G. and Loubere, R. High-Order C onservative R emapping with a posteriori MOOD stabilization on polygonal meshes. 2015
work page 2015
-
[14]
Lauritzen, P. and Erath, C. and Mittal, R. On simplifying `incremental remap'-based transport schemes. Journal of Computational Physics. 2011
work page 2011
-
[15]
Klima, M. and Kucharik, M. and Shashkov, M. Local error analysis and comparison of the swept- and intersection-based remapping methods. Communications in Computational Physics. 2017
work page 2017
-
[16]
Dukowicz, J. K. and Baumgardner, J. R. Incremental remapping as a transport/advection algorithm. Journal of Computational Physics. 2000
work page 2000
-
[17]
Kucharik, M. and Shashkov, M. Flux-based approach for conservative remap of multi-material quantities in 2D arbitrary L agrangian- E ulerian simulations. Finite V olumes for C omplex A pplications VI P roblems & P erspectives. 2011
work page 2011
-
[18]
Kucharik, M. and Shashkov, M. Conservative multi-material remap for staggered multi-material arbitrary L agrangian- E ulerian methods. Journal of Computational Physics. 2014
work page 2014
-
[19]
Loubere, R. and Shashkov, M. A subcell remapping method on staggered polygonal grids for arbitrary- L agrangian- E ulerian methods. Journal of Computational Physics. 2005
work page 2005
-
[20]
Margolin, L. G. and Shashkov, M. Second-order sign-preserving remapping on general grids. 2002
work page 2002
-
[21]
Mavriplis, D. J. Revisiting the least-squares procedure for gradient reconstruction on unstructured meshes. 23--26 June, 2003
work page 2003
-
[22]
Scovazzi, G. and Love, E. and Shashkov, M. Multi-scale Lagrangian shock hydrodynamics on Q1/P0 finite elements: T heoretical framework and two-dimensional computations. Computer Methods in Applied Mechanics and Engineering. 2008
work page 2008
-
[23]
Caramana, E. J. and Shashkov, M. J. Elimination of artificial grid distortion and hourglass-type motions by means of L agrangian subzonal masses and pressures. Journal of Computational Physics. 1998
work page 1998
-
[24]
An arbitrary L agrangian- E ulerian strategy to solve compressible fluid flows
Hoch, P. An arbitrary L agrangian- E ulerian strategy to solve compressible fluid flows. 2009
work page 2009
-
[25]
Conservative F inite- D ifference M ethods on G eneral G rids
Shashkov, M. Conservative F inite- D ifference M ethods on G eneral G rids. 1996
work page 1996
-
[26]
Knupp, P. M. Winslow smoothing on two-dimensional unstructured meshes. Engineering with Computers. 1999
work page 1999
-
[27]
Evaluation of the S edov-von N eumann- T aylor blast wave solution
Kamm, J. Evaluation of the S edov-von N eumann- T aylor blast wave solution. 2000
work page 2000
-
[28]
Taylor, G. I. and Green, A. E. Mechanism of the production of small eddies from large ones. Proceedings of The Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences. 1937
work page 1937
-
[29]
Hirt, C. W. and Amsden, A. A. and Cook, J. L. An arbitrary Lagrangian-Eulerian computing method for all flow speeds. J. Comput. Phys. 1974
work page 1974
-
[30]
Liska, R. and Shashkov, M. and Vachal, P. and Wendroff, B. and Author, A. B. and Author, B. B. and Author, C. C. Optimization-based synchronized flux-corrected conservative interpolation (remapping) of mass and momentum for arbitrary L agrangian- E ulerian methods. J. Comput. Phys. 2010
work page 2010
-
[31]
Benson, D. J. Computational methods in Lagrangian and E ulerian hydrocodes. Comput. Method. Appl. M. 1992
work page 1992
-
[32]
Conservative rezoning (remapping) for general quadrilateral meshes
Dukowicz, J. Conservative rezoning (remapping) for general quadrilateral meshes. J. Comput. Phys. 1984
work page 1984
-
[33]
Margolin, L. G. and Shashkov, M. Second-order sign-preserving conservative interpolation (remapping) on general grids. J. Comput. Phys. 2003
work page 2003
-
[34]
Kenamond, M. A. and Burton, D. E. Exact intersection remapping of multi-material domain-decomposed polygonal meshes. 2--6 Sept 2013
work page 2013
-
[35]
Burton, D. E. and Kenamond, M. A. and Morgan, N. R. and Carney, T. C. and Shashkov, M. J. and Author, A. B. An intersection based ALE scheme (xALE) for cell centered hydrodynamics (CCH). 2--6 Sept 2013
work page 2013
-
[36]
Berndt, M. and Breil, J. and Galera, S. and Kucharik, M. and Maire, P. H. and Shashkov, M. Two-step hybrid conservative remapping for multimaterial arbitrary L agrangian- E ulerian methods. J. Comput. Phys. 2011
work page 2011
-
[37]
Kucharik, M. and Shashkov, M. One-step hybrid remapping algorithm for multi-material arbitrary L agrangian- E ulerian methods. J. Comput. Phys. 2012
work page 2012
-
[38]
Breil, J. and Alcin, H. and Maire, P. H. A swept intersection-based remapping method for axisymmetric ReALE computation. Int. J. Numer. Math. 2015
work page 2015
-
[39]
Kucharik, M. and Shashkov, M. and Wendroff, B. An efficient linearity-and-bound-preserving remapping method. J. Comput. Phys. 2003
work page 2003
-
[40]
Lauritzen, P. and Erath, C. and Mittal, R. On simplifying `incremental remap'-based transport schemes. J. Comput. Phys. 2011
work page 2011
-
[41]
Klima, M. and Kucharik, M. and Shashkov, M. Local error analysis and comparison of the swept- and intersection-based remapping methods. Commun. Comput. Phys. 2017
work page 2017
-
[42]
Dukowicz, J. K. and Baumgardner, J. R. Incremental remapping as a transport/advection algorithm. J. Comput. Phys. 2000
work page 2000
-
[43]
Abrams, D. M. Conductive Polymers. 1973
work page 1973
- [44]
-
[45]
MacKay, D. M. Handbook of Sensory Physiology. 1973
work page 1973
-
[46]
Smith, S. E. Neuromuscular Junction. 1976
work page 1976
- [47]
-
[48]
Chung, S. T. and Morris, R. L. Abstracts of the 3rd International Symposium on the Genetics of Industrial Microorganisms. 4–9 June 1978
work page 1978
-
[49]
Kucharik, M. and Shashkov, M. Conservative multi-material remap for staggered multi-material arbitrary L agrangian- E ulerian methods. J. Comput. Phys. 2014
work page 2014
-
[50]
Loubere, R. and Shashkov, M. A subcell remapping method on staggered polygonal grids for arbitrary- L agrangian- E ulerian methods. J. Comput. Phys. 2005
work page 2005
-
[51]
Mavriplis, D. J. Revisiting the least-squares procedure for gradient reconstruction on unstructured meshes. 23--26 June 2003
work page 2003
-
[52]
Scovazzi, G. and Love, E. and Shashkov, M. Multi-scale L agrangian shock hydrodynamics on Q1/P0 finite elements: T heoretical framework and two-dimensional computations. Comput. Method Appl. M. 2008
work page 2008
-
[53]
Caramana, E. J. and Shashkov, M. J. Elimination of artificial grid distortion and hourglass-type motions by means of L agrangian subzonal masses and pressures. J. Comput. Phys. 1998
work page 1998
-
[54]
Knupp, P. M. Winslow smoothing on two-dimensional unstructured meshes. Eng. Comput. 1999
work page 1999
-
[55]
Taylor, G. I. and Green, A. E. Mechanism of the production of small eddies from large ones. P. Roy. Soc. Lond. A. Mat. 1937
work page 1937
-
[56]
ACM Transactions on Mathematical Software (TOMS) , volume=
Anatomy of high-performance matrix multiplication , author=. ACM Transactions on Mathematical Software (TOMS) , volume=. 2008 , publisher=
work page 2008
- [57]
-
[58]
Peters, A. and others , title =. Journal of Computational Physics , volume =
- [59]
-
[60]
Somasunderam, N. and Chandrasekaran, S. , title =. Linear Algebra and its Applications , volume =
-
[61]
Osorghin, N. and others , title =. arXiv preprint arXiv:2405.14288 , year =
-
[62]
Stuckermann, F. and others , title =. Nature Computational Science , volume =
-
[63]
Nested Dissection Solver for Transport in 3D Nano-Electronic Devices
Afzalian, A. and others , title =. arXiv preprint arXiv:1702.05167 , year =
work page internal anchor Pith review Pith/arXiv arXiv
-
[64]
Jiang, L. and others , title =. Journal of Applied Physics , volume =
-
[65]
An arbitrary L agrangian- E ulerian computing method for all flow speeds
Hirt, C W and Amsden, A A and Cook, J L. An arbitrary L agrangian- E ulerian computing method for all flow speeds. J C omput P hys. 1974
work page 1974
-
[66]
Computational methods in L agrangian and E ulerian hydrocodes
Benson, D J. Computational methods in L agrangian and E ulerian hydrocodes. Comput M ethod A ppl M. 1992
work page 1992
-
[67]
Conservative rezoning (remapping) for general quadrilateral meshes
Dukowicz, J. Conservative rezoning (remapping) for general quadrilateral meshes. J C omput P hys. 1984
work page 1984
-
[68]
Second-order sign-preserving conservative interpolation (remapping) on general grids
Margolin, L G and Shashkov, M. Second-order sign-preserving conservative interpolation (remapping) on general grids. J C omput P hys. 2003
work page 2003
-
[69]
Exact intersection remapping of multi-material domain-decomposed polygonal meshes
Kenamond, M A and Burton, D E. Exact intersection remapping of multi-material domain-decomposed polygonal meshes. September 2--6, 2013
work page 2013
-
[70]
An intersection based ALE scheme (xALE) for cell centered hydrodynamics (CCH)
Burton, D E and Kenamond, M A and Morgan, N R and Carney, T C and Shashkov, M J and Author, A B. An intersection based ALE scheme (xALE) for cell centered hydrodynamics (CCH). September 2--6, 2013
work page 2013
-
[71]
Two-step hybrid conservative remapping for multimaterial arbitrary L agrangian- E ulerian methods
Berndt, M and Breil, J and Galera, S and Kucharik, M and Maire, P H and Shashkov, M. Two-step hybrid conservative remapping for multimaterial arbitrary L agrangian- E ulerian methods. J C omput P hys. 2011
work page 2011
-
[72]
One-step hybrid remapping algorithm for multi-material arbitrary L agrangian- E ulerian methods
Kucharik, M and Shashkov, M. One-step hybrid remapping algorithm for multi-material arbitrary L agrangian- E ulerian methods. J C omput P hys. 2012
work page 2012
-
[73]
A swept intersection-based remapping method for axisymmetric ReALE computation
Breil, J and Alcin, H and Maire, P H. A swept intersection-based remapping method for axisymmetric ReALE computation. Int J N umer M eth F l. 2015
work page 2015
-
[74]
Numerical methods for gasdynamic systems on unstructured meshes
Barth, T J. Numerical methods for gasdynamic systems on unstructured meshes. An I ntroduction to R ecent D evelopments in T heory and N umerics for C onservation L aws, P roceedings of the I nternational S chool on T heory and N umerics for C onservation L aws. 1997
work page 1997
-
[75]
Liska, R and Shashkov, M and Vachal, P and Wendroff, B and Author, A B and Author, B B and Author, C C. Optimization-based synchronized flux-corrected conservative interpolation (remapping) of mass and momentum for arbitrary L agrangian- E ulerian methods. J C omput P hys. 2010
work page 2010
-
[76]
An efficient linearity-and-bound-preserving remapping method
Kucharik, M and Shashkov, M and Wendroff, B. An efficient linearity-and-bound-preserving remapping method. J C omput P hys. 2003
work page 2003
-
[77]
High-Order C onservative R emapping with a posteriori MOOD stabilization on polygonal meshes
Blanchard, G and Loubere, R. High-Order C onservative R emapping with a posteriori MOOD stabilization on polygonal meshes. 2015
work page 2015
-
[78]
On simplifying `incremental remap'-based transport schemes
Lauritzen, P and Erath, C and Mittal, R. On simplifying `incremental remap'-based transport schemes. J C omput P hys. 2011
work page 2011
-
[79]
Local error analysis and comparison of the swept- and intersection-based remapping methods
Klima, M and Kucharik, M and Shashkov, M. Local error analysis and comparison of the swept- and intersection-based remapping methods. Commun C omput P hys. 2017
work page 2017
-
[80]
Incremental remapping as a transport/advection algorithm
Dukowicz, J K and Baumgardner, J R. Incremental remapping as a transport/advection algorithm. J C omput P hys. 2000
work page 2000
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.