A polynomial dimension-dependence analysis of Bramble--Pasciak--Xu preconditioners

We investigate the dimension dependence of Bramble–Pasciak–Xu (BPX) preconditioners for high-dimensional partial differential equations and establish that the condition numbers of BPX-preconditioned systems grow only polynomially with the spatial dimension. Our analysis requires a careful derivation of the dimension dependence of several fundamental tools in the theory of finite element methods, including the elliptic regularity, Bramble–Hilbert lemma, trace inequalities, and inverse inequalities. We further introduce a new quasi-interpolation operator into finite element spaces, a variant of the classical Scott–Zhang interpolation, whose associated constants scale polynomially with the dimension. Building on these ingredients, we prove a multilevel norm equivalence theorem and derive a BPX preconditioner with explicit polynomial bounds on its dimensional dependence. This result has notable implications for emerging quantum computing methodologies: recent studies indicate that polynomial dependence of BPX preconditioners on dimension can yield exponential speedups for quantum-algorithmic approaches over their classical counterparts.