REVIEW 4 major objections 5 minor 18 references
A Sub-linear Low-Rank Solver for Poisson's Equation using Machine Learning Frameworks for GPU Acceleration
T0 review · 4 major / 5 minor · reviewed 2026-07-08 · grok-4.5
Pith's one-line read A low-rank Cross-DEIM Poisson solver runs at sub-linear cost on a single GPU
desk verdict Practical GPU low-rank Poisson solver via Cross-DEIM, leverage scores, and batched DST; solid engineering under a stated low-rank assumption. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
Cross-DEIM: an adaptive loop that alternates leverage-score index selection with a low-rank cross approximation of the residual or solution, each step solved by independent batched DSTs along each dimension. The leverage scores replace classical pivoted DEIM/QDEIM, and the warm start reuses previous indices so that the iteration converges with only a modest target rank.
What would settle it
Solve a Poisson problem whose exact solution is known to have rank that grows with mesh size (e.g., a non-separable high-frequency forcing) and check whether the Cross-DEIM residual still drops to the claimed tolerance at the same modest rank and sub-linear wall-clock cost; if the required rank or time scales like the full mesh, the central claim fails.
Extended reading notes
Core claim
For Poisson problems whose solution is low-rank, an adaptive warm-started Cross-DEIM iteration that uses leverage-score index selection, paired with a batched Discrete Sine Transform solver and implemented in PyTorch, yields a sub-linear-cost solver that enables previously infeasible problem sizes on a single A100 GPU.
Load-bearing premise
The solution (or residual) stays low-rank enough throughout the adaptive process that a modest fixed rank already gives acceptable accuracy; if the true rank grows with mesh size or dimension, the sub-linear scaling disappears.
Editorial extensions
If this is right
- Poisson problems that previously exceeded single-GPU memory become solvable once their solution rank is modest.
- The same PyTorch implementation runs unchanged on CPU or GPU, so performance can be measured without rewriting kernels.
- Batched DSTs avoid global transposes even in three or more dimensions, removing a classic communication bottleneck.
- Leverage-score index selection is cheaper than pivoted DEIM/QDEIM while still producing a usable cross approximation.
- Warm-started index reuse reduces the number of outer iterations needed for a given accuracy.
Reading between the lines
- The same Cross-DEIM + batched-transform pattern could be tried on other separable elliptic operators (Helmholtz, screened Poisson) whose Green’s functions admit low-rank structure.
- If leverage scores remain effective, the method may extend to time-dependent problems by treating each time slice as a warm-started low-rank update.
- A practical test would be to replace the pure DST with a low-rank-friendly multigrid or spectral-element backend and measure whether the sub-linear regime survives.
- Memory savings from never forming the full residual could let the same GPU host higher-dimensional (4-D+) tensor-product Poisson problems that currently require distributed memory.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript proposes a Poisson solver specialized to problems whose solution is low-rank. It builds an adaptive, warm-started Cross-DEIM iteration that alternates leverage-score index selection with cross approximation, then recovers the factors with a batched Discrete Sine Transform (DST) so that FFTs run independently along each dimension without a global transpose. The algorithm is implemented in PyTorch to obtain portable GPU acceleration. On an A100 GPU and an AMD EPYC CPU the authors report timings that they interpret as sub-linear cost and as enabling problem sizes previously infeasible on a single accelerator. The target rank, leverage-sample count, and adaptation schedule are free algorithmic parameters; accuracy is assessed against residual or reference solutions rather than by fitting free parameters to the PDE residual.
Significance. If the low-rank premise holds and the adaptive Cross-DEIM process keeps the working rank modest, the combination of leverage-score cross approximation with batched DST is a practically useful route to large Poisson solves on a single GPU, and the PyTorch realization lowers the barrier to GPU use for classical numerical linear algebra. The explicit scoping to low-rank solutions, the avoidance of global transposes in higher dimensions, and the concrete A100/EPYC measurements are genuine strengths. The contribution is primarily algorithmic and systems-oriented rather than a new existence theory; its impact therefore hinges on demonstrated rank stability and on clear baselines for the “previously infeasible” claim.
major comments (4)
- [Abstract / Introduction / Performance results] The central claim of sub-linear cost (abstract and introduction) is load-bearing only while the working rank r needed for a fixed residual remains modest as mesh size n (and dimension) grow. The manuscript does not appear to contain a systematic residual-versus-rank or achieved-rank-versus-n study at fixed accuracy across the large A100 problem sizes used for the feasibility claim. Without that evidence the asymptotic and practical sub-linearity statements rest on the structural premise rather than on demonstrated behavior of the adaptive process.
- [Index-selection / Cross-DEIM method section] Leverage-score index selection is adopted in place of the historically preferred DEIM/QDEIM pivots because of cost. The quality of the selected indices directly controls the rank (or iteration count) required for a target residual. A head-to-head comparison—same residual tolerance, same warm-start schedule—of ranks and wall-clock time for leverage scores versus DEIM/QDEIM on the reported problem sizes is needed to show that the cheaper selector does not inflate r enough to erase the claimed gains.
- [Performance / numerical results section] The assertion that the approach “enables problem sizes that previously were not feasible” requires explicit baselines: memory footprint and runtime of a full-grid DST (or of a competing low-rank method) at the same n, together with the point at which those baselines exhaust A100 memory or time. Selected timings alone do not establish the feasibility frontier.
- [Algorithm parameters / experiments] The free parameters (target rank r, leverage-score sample count, warm-start and adaptation schedule) are acknowledged but their sensitivity is not quantified. A short ablation showing residual and runtime versus these knobs on at least one large instance would make the practical claims reproducible and would bound the risk that favorable settings were chosen only for the reported sizes.
minor comments (5)
- [Complexity discussion] Clarify the precise complexity model: state the leading-term cost as a function of n, d, r and the leverage sample size so that “sub-linear” is unambiguous relative to a full-grid O(n^d log n) DST.
- [Algorithm / numerical results] Define the residual norm and the stopping criterion for the adaptive Cross-DEIM loop explicitly (absolute vs relative, which residual), and report it consistently in all tables/figures.
- [Reproducibility / software] If code or scripts used for the A100/EPYC timings can be released, a short availability statement would substantially strengthen reproducibility of the performance claims.
- [Figures and tables] Ensure that figure axes and table captions state mesh size, dimension, target residual, and hardware (A100 vs EPYC) so that each plot is self-contained.
- [Abstract and throughout] Minor prose: “and and cross approximation” in the abstract; check for similar doubled words and for consistent hyphenation of “low-rank” / “sub-linear”.
Simulated Author's Rebuttal
We thank the referee for a careful and constructive report. The four major comments correctly identify where the manuscript’s claims about sub-linearity, index-selection quality, feasibility frontiers, and parameter sensitivity need stronger empirical support. We agree that residual-versus-rank and rank-versus-n studies, a leverage-score versus DEIM/QDEIM comparison, explicit full-grid and competing low-rank baselines, and a short ablation of free parameters are necessary. We will add these experiments and the corresponding discussion in the revised manuscript, and we will temper the wording of the sub-linearity and “previously infeasible” claims so that they rest on the new evidence rather than on the structural premise alone. Below we answer each major comment point by point and indicate the revisions we will make.
read point-by-point responses
-
Referee: [Abstract / Introduction / Performance results] The central claim of sub-linear cost (abstract and introduction) is load-bearing only while the working rank r needed for a fixed residual remains modest as mesh size n (and dimension) grow. The manuscript does not appear to contain a systematic residual-versus-rank or achieved-rank-versus-n study at fixed accuracy across the large A100 problem sizes used for the feasibility claim. Without that evidence the asymptotic and practical sub-linearity statements rest on the structural premise rather than on demonstrated behavior of the adaptive process.
Authors: We agree that the sub-linearity claim is load-bearing only when the adaptive Cross-DEIM process keeps the working rank modest at fixed residual as n grows, and that the current manuscript does not supply a systematic residual-versus-rank or achieved-rank-versus-n study on the large A100 sizes. We will add such a study: for representative 2-D and 3-D Poisson problems with known low-rank structure we will report residual (and, where available, error against a reference) as a function of target rank r, and the rank required to meet fixed residual tolerances as a function of n up to the largest sizes used in the performance section. We will also report the rank trajectory of the adaptive/warm-started iteration. On the basis of those data we will revise the abstract and introduction so that “sub-linear cost” is stated only where the measured ranks remain essentially independent of n (or grow slowly enough that the observed complexity remains sub-linear), and we will qualify the claim when the premise is only structural. revision_made = yes. revision: yes
-
Referee: [Index-selection / Cross-DEIM method section] Leverage-score index selection is adopted in place of the historically preferred DEIM/QDEIM pivots because of cost. The quality of the selected indices directly controls the rank (or iteration count) required for a target residual. A head-to-head comparison—same residual tolerance, same warm-start schedule—of ranks and wall-clock time for leverage scores versus DEIM/QDEIM on the reported problem sizes is needed to show that the cheaper selector does not inflate r enough to erase the claimed gains.
Authors: The referee is right that a head-to-head comparison is needed. We chose leverage scores because full DEIM/QDEIM pivots become expensive at the ranks and dimensions we target, but we have not yet shown that the cheaper selector does not inflate r (or iteration count) enough to erase the gains. In the revision we will implement DEIM and QDEIM index selection within the same Cross-DEIM / warm-start framework and, for the same residual tolerances and adaptation schedule, report achieved rank, number of outer iterations, and wall-clock time (CPU and A100) against leverage-score selection on the problem sizes used in the performance section. Where DEIM/QDEIM remain feasible we will also report the cost of the selection step alone. The text will state clearly whether leverage scores preserve the claimed advantage or under what regimes DEIM/QDEIM remain preferable. revision_made = yes. revision: yes
-
Referee: [Performance / numerical results section] The assertion that the approach “enables problem sizes that previously were not feasible” requires explicit baselines: memory footprint and runtime of a full-grid DST (or of a competing low-rank method) at the same n, together with the point at which those baselines exhaust A100 memory or time. Selected timings alone do not establish the feasibility frontier.
Authors: We agree that selected timings of our method alone do not establish a feasibility frontier. We will add explicit baselines: (i) memory footprint and runtime of a full-grid (dense) DST Poisson solve at the same n, including the largest n for which the dense grid still fits in A100 memory and the n at which it exhausts memory or becomes impractical in time; (ii) where applicable, a competing low-rank approach (e.g., a non-adaptive cross or HODLR/H-matrix style Poisson solve if available in a comparable setting) with the same residual target. We will tabulate or plot memory and time versus n for our method and the baselines, and we will rewrite the “previously not feasible” claim so that it is tied to the measured crossover points rather than left as an informal assertion. revision_made = yes. revision: yes
-
Referee: [Algorithm parameters / experiments] The free parameters (target rank r, leverage-score sample count, warm-start and adaptation schedule) are acknowledged but their sensitivity is not quantified. A short ablation showing residual and runtime versus these knobs on at least one large instance would make the practical claims reproducible and would bound the risk that favorable settings were chosen only for the reported sizes.
Authors: We agree that sensitivity of residual and runtime to the free parameters must be quantified. We will add a short ablation on at least one large 2-D and one large 3-D instance: residual and wall-clock time versus target rank r, versus leverage-score sample count, and versus warm-start / adaptation schedule (including a cold-start baseline). Default settings used in the main tables will be marked on those plots, and the text will state the ranges over which residual and time remain stable. This will make the practical claims more reproducible and will bound the risk that favorable knobs were chosen only for the reported sizes. revision_made = yes. revision: yes
Circularity Check
No significant circularity: sub-linear Cross-DEIM Poisson solver is a self-contained algorithmic construction with residual-based accuracy, not a fitted or self-definitional prediction.
full rationale
The paper presents an algorithmic method (adaptive warm-started Cross-DEIM with leverage-score index selection + batched DST in PyTorch) for Poisson problems whose solutions are assumed low-rank. Cost and feasibility claims are scoped to that problem class and are measured by residual/accuracy versus rank and wall-clock on A100/EPYC; rank is a user/algorithm parameter, not a free parameter fitted to produce a claimed physical prediction. There is no uniqueness theorem imported from the authors, no ansatz smuggled via self-citation that forces the result, and no renaming of a known empirical law as a first-principles derivation. Classical DST/FFT and cross-approximation ingredients are standard; the contribution is the combination, GPU implementation, and leverage-score choice for cost. Minor self-reference (authors choosing heuristics) is normal engineering and not load-bearing circularity. Score 0 is appropriate: the derivation is self-contained against external residual/runtime benchmarks and does not reduce by construction to its inputs.
Assumptions & free parameters
free parameters (3)
- target_rank_r
- leverage_score_sample_count
- warm_start_and_adaptation_schedule
assumptions (4)
- standard math The discrete Poisson operator with Dirichlet boundaries is diagonalized by the Discrete Sine Transform (or multi-D tensor product of DSTs).
- standard math A matrix/tensor that is exactly or approximately rank-r admits an accurate cross approximation from r well-chosen rows and columns (plus intersection).
- domain assumption Statistical leverage scores yield index sets of quality comparable to pivoted DEIM/QDEIM for the purposes of this solver, at lower asymptotic cost.
- domain assumption The Poisson solution (or residual) of interest is low-rank or admits a rapidly decaying singular spectrum.
Cite this review
Pith. "Pith review of A Sub-linear Low-Rank Solver for Poisson's Equation using Machine Learning Frameworks for GPU Acceleration." pith.science (2026). https://pith.science/paper/FEUSRGRS
@misc{pith2026260706021,
author = {Pith},
title = {Pith review of: A Sub-linear Low-Rank Solver for Poisson's Equation using Machine Learning Frameworks for GPU Acceleration},
year = {2026},
howpublished = {\url{https://pith.science/paper/FEUSRGRS}},
note = {Machine review of arXiv:2607.06021}
}
read the original abstract
In this paper we explore a fast Poisson solver for problems with a solution that is known to be low-rank. We use an adaptive and warm started cross approximation called Cross-DEIM that iterates between index selection and and cross approximation to generate a low-rank solution. This paper focuses on leveraging a modern machine learning framework, PyTorch, as a general purpose array language to implement low-rank solvers based on Cross-DEIM. PyTorch enables native access to GPUs and accelerators but with a user-friendly high-level interface. We investigate statistical leverage scores for the index selection for the cross approximation due to the cost associated with the pivoted algorithms used with the discrete empirical interpolation methods (DEIM and QDEIM) which are historically preferred. The cross approximation is naturally paired with a Discrete Sine Transform (DST) Poisson solver. This allows the Fast Fourier Transform (FFT) to be evaluated in batches along dimensions independently without any global transpose even in higher dimensions. We present performance results running on a A100 GPU and AMD EPYC CPU demonstrating the usefulness of the approach that enables problems sizes that previously were not feasible.
Figures
Figures from the paper (4 more)
Reference graph
Works this paper leans on
-
[1]
Modular. [n. d.]. mojo, powerful cpu+gpu programming.,https://www.modular. com/mojo
-
[2]
In: Pro- ceedings of the 12th USENIX Conference on Operating Systems Design and Im- plementation
Abadi, M., Barham, P., Chen, J., Chen, Z., Davis, A., Dean, J., Devin, M., Ghe- mawat, S., Irving, G., Isard, M., Kudlur, M., Levenberg, J., Monga, R., Moore, S., Murray, D.G., Steiner, B., Tucker, P., Vasudevan, V., Warden, P., Wicke, M., Yu, Y., Zheng, X.: Tensorflow: a system for large-scale machine learning. In: Pro- ceedings of the 12th USENIX Confer...
work page 2016
-
[3]
The International Journal of High Performance Computing Applications38(5), 468–490 (2024)
Abdelfattah, A., Beams, N., Carson, R., Ghysels, P., Kolev, T., Stitt, T., Vargas, A., Tomov, S., Dongarra, J.: MAGMA: Enabling exascale performance with ac- celerated BLAS and LAPACK for diverse GPU architectures. The International Journal of High Performance Computing Applications38(5), 468–490 (2024)
work page 2024
-
[4]
lrAA: Low-Rank Anderson Acceleration
Appelo, D., Cheng, Y.: lraa: Low-rank anderson acceleration. arXiv preprint arXiv:2503.03909 (2025)
work page Pith review arXiv 2025
-
[5]
Acta Numerica32, 1–121 (2023).https://doi.org/10.1017/S0962492922000125
Bachmayr, M.: Low-rank tensor methods for partial differential equations. Acta Numerica32, 1–121 (2023).https://doi.org/10.1017/S0962492922000125
-
[6]
Cambridge University Press (2025)
Ballard, G., Kolda, T.G.: Tensor Decompositions for Data Science. Cambridge University Press (2025)
work page 2025
-
[7]
Bradbury, J., Frostig, R., Hawkins, P., Johnson, M.J., Katariya, Y., Leary, C., Maclaurin, D., Necula, G., Paszke, A., VanderPlas, J., Wanderman-Milne, S., Zhang, Q.: JAX: composable transformations of Python+NumPy programs (2018), http://github.com/jax-ml/jax
work page 2018
-
[8]
SIAM Journal on Scientific Computing32(5), 2737–2764 (2010)
Chaturantabut, S., Sorensen, D.C.: Nonlinear model reduction via discrete empiri- cal interpolation. SIAM Journal on Scientific Computing32(5), 2737–2764 (2010)
work page 2010
Show all 18 references
-
[9]
Demmel,J.W.:Appliednumericallinearalgebra.SocietyforIndustrialandApplied Mathematics (1997)
1997
-
[10]
Proceedings of the Royal Society A479(2278), 20230320 (2023)
Donello, M., Palkar, G., Naderi, M., Del Rey Fernández, D., Babaee, H.: Oblique projection for scalable rank-adaptive reduced-order modelling of nonlinear stochas- tic partial differential equations with time-dependent bases. Proceedings of the Royal Society A479(2278), 202303...
2023
-
[11]
SIAM Journal on Scientific Computing38(2), A631–A648 (2016).https://doi.org/10.1137/ 15M1019271
Drmač, Z., Gugercin, S.: A new selection operator for the discrete empirical inter- polation method—improved a priori error bound and extensions. SIAM Journal on Scientific Computing38(2), A631–A648 (2016).https://doi.org/10.1137/ 15M1019271
2016
-
[12]
Contemporary Mathematics280, 47–52 (2001)
Goreinov, S.A., Tyrtyshnikov, E.E.: The maximal-volume concept in approxima- tion by low-rank matrices. Contemporary Mathematics280, 47–52 (2001)
2001
-
[13]
Linear algebra and its applications261(1-3), 1–21 (1997) 16 M
Goreinov,S.A.,Tyrtyshnikov,E.E.,Zamarashkin,N.L.:Atheoryofpseudoskeleton approximations. Linear algebra and its applications261(1-3), 1–21 (1997) 16 M. I. Andersson and D. Appelö
1997
-
[14]
Proceedings of the National Academy of Sciences106(3), 697–702 (2009)
Mahoney, M.W., Drineas, P.: Cur matrix decompositions for improved data anal- ysis. Proceedings of the National Academy of Sciences106(3), 697–702 (2009). https://doi.org/10.1073/pnas.0803205106
2009 doi
-
[15]
In: NIPS-W (2017)
Paszke, A., Gross, S., Chintala, S., Chanan, G., Yang, E., DeVito, Z., Lin, Z., Desmaison, A., Antiga, L., Lerer, A.: Automatic differentiation in PyTorch. In: NIPS-W (2017)
2017
-
[16]
Advances in neural information processing sys- tems32(2019)
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., et al.: Pytorch: An imperative style, high- performance deep learning library. Advances in neural information processing sys- tems32(2019)
2019
-
[17]
Pulliam, T.H., Zingg, D.W.: Fundamentals of computational fluid dynamics, vol. 246. Springer
-
[18]
Artech House, Boston, 3rd edn
Taflove, A., Hagness, S.C.: Computational electrodynamics: the finite-difference time-domain method. Artech House, Boston, 3rd edn. (2005)
2005
Reviewed July 8, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.