A wavelet basis is a set of localized, multi-scale building blocks for representing signals or operators. Designing one forces a known compromise. With a real scalar wavelet you cannot have orthogonality (exact, stable inversion), compact support (short filters, linear cost) and symmetry (a mirror-symmetric filter, so no phase distortion) all at once, except for the discontinuous Haar basis. The usual responses are to give up symmetry (Daubechies), to give up orthogonality in favour of two dual bases (biorthogonal), or to add degrees of freedom through multiwavelets or higher dilation. Numerical linear algebra has its own symmetry wall. Fast, reliable solvers and preconditioners are mature for symmetric positive definite matrices. For non-symmetric matrices, such as those from advection-dominated flow, directed graphs, or circuits, preconditioners remain brittle. Incomplete LU fails to construct on roughly 40% of a large set of real non-symmetric matrices, and learned graph-network preconditioners must be retrained for every matrix.
This note proposes that the two walls answer each other. A non-symmetric operator has different row and column structure, so it should be compressed by two different multiresolution bases, one on each side. For transport operators, the symmetry that wavelet designers usually fight to keep is the wrong target. Asymmetric, direction-aligned filters on the test side should make the inverse of the operator sparser. We would build a fast preconditioner for the generalized minimal residual method (GMRES), the standard Krylov solver for non-symmetric systems, from a two-sided biorthogonal wavelet transform with independently chosen left and right filter banks. We would test whether this choice of filter symmetry measurably changes solver convergence as the problem moves from symmetric (pure diffusion) to strongly non-symmetric (advection-dominated).
Core Claim
Let $A$ be an $N\times N$ non-symmetric sparse matrix from a structured-grid discretization. Let $W_L$ and $W_R$ be two fast, compactly supported, invertible multiresolution transforms: an analysis transform applied to residuals and a synthesis transform for the solution. We form the transformed operator $\hat A = W_L A W_R^{-1}$. We compute a sparse approximate inverse $G$ of $\hat A$ on a prescribed sparsity pattern $S$:
$$G^\star=\arg\min_{G:\,\mathrm{supp}(G)\subseteq S}\ \|I-\hat A G\|_F,$$
and we precondition GMRES with $M^{-1}=W_R^{-1}G^\star W_L$. Each application costs $O(N)$ for the two transforms plus $O(|S|)$ for $G^\star$. The minimization splits into independent small least-squares problems, one per column. Unlike incomplete LU, it has no pivots and so no pivot breakdown.
The claim has two parts. The first part is that the inverse of $A$ is far more compressible in a two-sided multiscale basis than in the original grid basis. A fixed budget $|S|$ therefore captures long-range coupling that local methods miss. This directly targets the non-locality that Trifonov proved: perturbing one entry of a tridiagonal matrix changes every entry of its triangular factor, which is why local message-passing networks fail to learn factorizations.
The second part, and the genuinely new one, concerns how the filters should be chosen once $A$ is non-symmetric. Choosing $W_L\neq W_R$ and allowing the left filters to be asymmetric (phase-shifted toward the downwind direction) should beat the symmetric, linear-phase biorthogonal filters normally preferred. The advantage should grow with the Péclet number, the ratio of advection to diffusion. In the pure-diffusion limit it should vanish, because there $A$ is symmetric and the classical trilemma preferences apply again.
Relation to Prior Work
The closest work is Asymmetric Multiresolution Matrix Factorization. It factors a non-symmetric matrix as $PHQ^T$ with separate greedy sequences of Givens rotations for rows and columns. It reports beating CUR in "100% of cases at 1% compression" on 70 UFlorida matrices. That paper supplies the key insight that left and right sides deserve different multiscale bases. Our proposal differs in three ways. We use fixed-cost filter-bank transforms instead of an expensive greedy rotation search. We compress the inverse rather than the matrix. We evaluate solver convergence rather than reconstruction error, an application the AMMF authors leave unexplored.
The filter design draws on wavelet construction work. Biorthogonal systems (Generalized biorthogonal Daubechies wavelets) let both primal and dual filters be short and symmetric, and also allow exact reproduction of exponential polynomials $P(t)e^{\alpha t}$. This matters because the boundary layers of 1D advection-diffusion are exactly such exponentials. Tuning $\alpha$ to the local Péclet number is therefore a principled way to build the right basis. Their non-convergence caveat for arbitrary complex $\alpha$ constrains which values we may use. The lossless state-space parameterization of Karel et al. gives a smooth, low-dimensional family of filters, which we would optimize over. Their observation that unbalanced multiwavelets leak smooth signals into detail coefficients is a warning we test directly.
Multiwavelet-based Operator Learning and its coupled extension show that vanishing moments compress PDE kernels. However, both learn forward surrogates with a single fixed compact basis and never build algebraic preconditioners.
On the solver side, three lines motivate the gap. Graph Neural Preconditioners handle non-symmetric matrices inside flexible GMRES but train one network per matrix and have no multiscale structure. Learned incomplete factorizations for GMRES shape singular values but are restricted to the ILU(0) pattern and local message passing. Constrained lAIR shows that non-symmetric multigrid needs restriction different from transposed interpolation ($R\neq P^T$). That is the algebraic counterpart of $W_L\neq W_R$, but it builds these operators by local heuristic minimization rather than from filter banks with known moment properties.
The SPD-only neural multigrid of Lyu et al. constrains the design. It shows that keeping a classical algorithmic backbone and learning only a little is what scales. Accordingly, we learn at most a handful of filter parameters per problem family, never per matrix.
We note that wavelet-compressed approximate inverses for elliptic, symmetric problems are an older classical idea that is not indexed in this file. Our contribution is not wavelet preconditioning as such. It is the bilateral, symmetry-broken filter choice for non-symmetric operators and the test of whether that choice matters.
Research Program
We would first build the transform library. It would contain CDF-type symmetric biorthogonal pairs, orthogonal Daubechies filters (asymmetric), the exponential-reproducing non-stationary biorthogonal filters with $\alpha$ tied to the Péclet number, and the dilation-4 symmetric orthonormal filters of Bin Han as a test of whether the higher-dilation escape from the trilemma helps. Each would be used as $W_L$, $W_R$, or both, giving symmetric-same-both-sides, symmetric-different, and asymmetric-left configurations. In 2D and 3D we use tensor products aligned with the grid. Directional systems such as shearlets are left for later work.
The core diagnostic is the compressibility of $A^{-1}$. For moderate $N$, where the inverse can be formed, we measure the number of wavelet-domain entries needed to capture 99% of its Frobenius energy. We then ask whether this number predicts GMRES iteration counts across filter choices. If it does, filters can be chosen cheaply, without running solves.
We then make the filter choice transfer across problems. The few continuous filter parameters (lattice angles from the Karel parameterization, plus $\alpha$) are tuned on small grids of one problem family to minimize the compressibility proxy. They are then frozen and applied zero-shot to larger grids and new coefficient fields. This addresses the per-matrix retraining that GNP leaves open.
Baselines
The naive reference point is unpreconditioned restarted GMRES and GMRES with ILU(0). On SuiteSparse non-SPD matrices, ILU is reported to fail to construct on "~40% of the test cases" (GNP). Our method cannot break down on pivots, so we will report its construction failure rate alongside iteration counts.
The strongest classical competitor on advection-diffusion is non-symmetric algebraic multigrid: lAIR and ClAIR from Constrained Local Approximate Ideal Restriction, used as a GMRES preconditioner. That paper reports operator complexity "1.34-1.51" for ClAIR against "2.20-2.87" for lAIR on diffusion-dominated grids. No reported GMRES iteration counts for ClAIR were found on Lacuna, so we will run it ourselves. ClAIR and lAIR will run on identical matrices with their default coarsening, under the same relative-residual tolerance ($10^{-8}$) and GMRES restart length. We will match stored nonzeros by tuning our pattern $S$ so that the preconditioner's nonzeros relative to $\mathrm{nnz}(A)$ fall in ClAIR's complexity range. Beating ClAIR means fewer iterations or lower setup-plus-solve time at equal memory in the advection-dominated regime, while staying within a constant factor in the diffusion-dominated regime.
The strongest learned competitor is GNP inside flexible GMRES, which was top-performing on "13.7% to 19.4% of the 800+ matrices tested" (GNP). It will be trained per matrix with its published recipe. We will compare total wall-clock including its training time, since our method needs only a sparse least-squares setup.
On the synthetic non-symmetric Poisson benchmark ($n=2{,}500$), the learned ILU with $\mathcal{L}_{max}$ loss reaches a preconditioned condition number "$\kappa \approx 16,139$" (Learning incomplete factorization preconditioners for GMRES). Matching or lowering this at equal nonzeros, without any training, counts as beating it.
Two ablations isolate the key ingredients. The first is a grid-domain sparse approximate inverse with the same nonzero budget ($W_L=W_R=I$), which isolates multiresolution. The second is the same two-sided scheme with symmetric filters on both sides, which isolates the symmetry-breaking choice and is the decisive control for the core claim.
Why not just…?
Why not just use non-symmetric algebraic multigrid such as ClAIR? It is the real threat on structured advection-diffusion. It may well win in iteration count, since multigrid is typically near-optimal there. Our case rests on three things: no setup heuristics, guaranteed construction, and a cheap, analyzable filter choice. If ClAIR dominates at equal memory across the Péclet sweep, the honest conclusion is that two-sided wavelets are a compression result rather than a solver result, and we would report that.
Why not just use one good symmetric biorthogonal wavelet on both sides? This is the most likely way the core claim fails. Symmetric CDF filters have more vanishing moments per filter length, and that alone may dominate compressibility. The symmetric-both-sides ablation across Péclet numbers settles it. Our hypothesis predicts a gap that grows with Péclet and closes at zero. A flat gap refutes the symmetry-breaking claim and leaves only the generic multiresolution benefit.
Why not just symmetrize, via the block embedding with $A$ and $A^T$ or the normal equations, and use symmetric solvers? The normal equations square the condition number. The block embedding doubles dimension and produces an indefinite spectrum symmetric about zero, so the mature SPD machinery (conjugate gradients, SPD multigrid like Lyu et al.) does not apply directly. We will include MINRES on the block embedding with a symmetric wavelet preconditioner as an extra baseline, to measure this cost rather than assume it.
Why not just reuse AMMF's learned Givens bases as the preconditioner? AMMF fits the bases to $A$, not to its inverse, and its greedy search is costly. We will run AMMF-based approximate inverses on the matrices where its search is feasible. This tests whether data-adapted discrete bases beat fixed filter banks, which would argue for a hybrid.
Proposed Experiments
The primary testbed is 2D and 3D advection-diffusion on structured grids with upwind and centred discretizations, sweeping the Péclet number from 0 to strongly advection-dominated, at grid sizes from $64^2$ to $1024^2$. It also includes the non-symmetric perturbed Poisson matrices of the learned-ILU paper at $n=2{,}500$. As a secondary stress test we use the structured-grid subset of the 867 SuiteSparse non-SPD matrices from the GNP study and, for compressibility, the 70 UFlorida matrices from AMMF. On unstructured SuiteSparse matrices we expect no advantage, since the method needs grid geometry, and we will report that boundary honestly.
The metrics are GMRES iterations to $10^{-8}$ relative residual, setup and solve wall-clock, preconditioner nonzeros relative to $\mathrm{nnz}(A)$, construction failure rate, and the 99%-energy compressibility of $A^{-1}$.
The checks are as follows. First, the asymmetric-left configuration must beat the symmetric-both-sides configuration by a margin that increases monotonically with Péclet and vanishes at zero. Second, compressibility rank must correlate with iteration-count rank across filter choices; we would require a Spearman correlation above 0.8 before relying on it for filter selection. Third, filters tuned on $64^2$ grids must keep their advantage at $1024^2$ without retuning. Fourth, the wavelet-domain inverse must beat the grid-domain inverse at equal nonzeros, confirming that a multiscale basis sidesteps the non-locality that defeats local learned factorizations. Failure of the first check with success of the fourth would reduce the project to a solid but modest result. Failure of both would end it.
References
- Message-Passing GNNs Fail to Approximate Sparse Triangular Factorizations
- Asymmetric Multiresolution Matrix Factorization
- Generalized biorthogonal Daubechies wavelets
- The Design of Matched Balanced Orthogonal Multiwavelets
- Multiwavelet-based Operator Learning for Differential Equations
- Coupled Multiwavelet Operator Learning for Coupled Differential Equations
- Graph Neural Preconditioners for Iterative Solutions of Sparse Linear Systems
- Learning incomplete factorization preconditioners for GMRES
- Constrained Local Approximate Ideal Restriction for Advection-Diffusion Problems
- A Multigrid-inspired Neural Iterative Solver for Poisson Equations on Large Voxel Grids
- Compactly supported orthonormal complex wavelets with dilation 4 and symmetry