Finite-Band Polynomial Seed Bank
Implementation & benchmark of arXiv:2607.05294 — Polynomial Initial-State Jumps and Christoffel Transforms in Krylov Complexity
Source paper: Polynomial Initial-State Jumps and Christoffel Transforms in Krylov Complexity arXiv:2607.05294 ⓘ · analyzed Aug 31, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Construct one reference Lanczos basis for a symmetric propagation operator H, then derive several seed-specific spectral responses for Q_a(H)x_0 through finite-band polynomial connectors. With degree-r seeds, each transformed basis vector uses at most 2r+1 neighboring reference basis vectors, avoiding a separate Lanczos factorization for every seed.
Formulas
Mathematical statement
Let H be a self-adjoint matrix, x_0 a reference cyclic vector, and d\mu(E) its spectral measure. Let P_n be monic orthogonal polynomials for \mu, with squared norms h_n, and let the reference Lanczos recurrence be H P_n(H)x_0=b_{n+1}P_{n+1}(H)x_0+a_nP_n(H)x_0+b_nP_{n-1}(H)x_0. For a polynomial Q of degree r, the prepared seed x_Q=N_Q^{-1/2}Q(H)x_0 has reweighted measure d\mu_Q(E)=|Q(E)|^2d\mu(E)/N_Q, where N_Q=\langle x_0,Q(H)^2x_0\rangle. The new monic orthogonal polynomial \widetilde P_n for \mu_Q is a finite connector of the reference polynomials: \widetilde P_n(E)=\sum_{j=0}^{2r}\Gamma_{n,n+j}P_{n+j}(E), with \Gamma_{n,n}=1. For a factored Q with roots \xi_a, the coefficients are determined by the finite Christoffel system imposing zeros and derivative constraints at repeated roots. This finite bandwidth, rather than a generic dense basis change, is the computational property transferred to the neural module.
Implementation notes
Integrate the method as a spectral propagation block in a graph neural network or linear state-space layer. Inputs are a symmetric normalized graph operator H, node features X, a reference seed x_0, propagation depth L, and a bank of learned low-degree polynomials Q_a(E)=\sum_{k=0}^r q_{a,k}E^k, initially with r=1 or r=2. Run Lanczos once on H and x_0, storing the tridiagonal coefficients a_n,b_n and reference responses Z_n=P_n(H)X. Estimate the moments needed for N_{Q_a}=\langle x_0,Q_a(H)^2x_0\rangle from the Lanczos tridiagonal or from short recurrence evaluations. For each seed, construct a small connector system from the orthogonality conditions under the reweighted measure; if Q_a is represented by roots, use the displayed Christoffel zero and derivative constraints, otherwise estimate the Gram matrix G_{ij}=\int Q_a(E)^2P_i(E)P_j(E)d\mu(E) by Gauss quadrature from the Lanczos tridiagonal. Solve for the coefficients \Gamma_{a,n,n+j}, then form Ztilde_{a,n}=N_{Q_a}^{-1/2}\sum_{j=0}^{2r}\Gamma_{a,n,n+j}Z_{n+j}. Concatenate the seed channels or combine them with a learned softmax gate before the graph readout. Pseudocode is: build T from a_n,b_n; compute quadrature nodes and weights; evaluate P_n and Q_a; solve each small connector system; apply the width-2r sliding transform to Z; normalize and gate. The mathematics supplies the finite-band form and normalization, while quadrature and connector conditioning are estimated numerically. First test on a 2-layer GCN or spectral graph model on Cora with L=32 and four degree-2 seeds. Compare against independently rerunning Lanczos for each seed and against ordinary Chebyshev features. Measure preprocessing time, peak memory, output relative error, and validation accuracy. A useful success criterion is at least 3x lower basis-construction cost, less than 1e-3 relative feature error versus separate Lanczos, and equal or improved validation accuracy.
Verification
This idea has not been verified yet.
Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.
Artifacts
Artifacts unavailable.