pith. sign in

arxiv: 1907.05773 · v1 · pith:QLBUQA7Dnew · submitted 2019-07-12 · 🧮 math.NA · cs.NA

Structured inversion of the Bernstein mass matrix

Larray Allen , Robert C. Kirby This is my paper

Pith reviewed 2026-05-24 22:23 UTC · model grok-4.3

classification 🧮 math.NA cs.NA
keywords Bernstein polynomialsmass matrixmatrix inversioneigendecompositionfinite element methodsconditioningroundoff errorHankel matrix
0
0 comments X

The pith

The univariate Bernstein mass matrix admits an explicit eigendecomposition constructible in O(n²) operations whose linear-system accuracy matches Cholesky factorization.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes several structured methods for inverting the univariate Bernstein mass matrix that rely on closed-form inverse entries, decompositions into Hankel, Toeplitz, and diagonal factors, and an explicit spectral decomposition. The eigendecomposition can be built in quadratic time and produces solutions whose accuracy is comparable to the Cholesky factorization. When roundoff error is measured by its effect on polynomials in the L² norm rather than the standard vector 2-norm, the effective conditioning is shown to be substantially milder. These results matter for finite-element and approximation algorithms that repeatedly solve mass-matrix systems on intervals or simplices.

Core claim

The univariate Bernstein mass matrix admits closed-form inverse entries together with decompositions into products of Hankel, Toeplitz, and diagonal matrices; its eigendecomposition can be constructed explicitly in O(n²) operations and yields linear-system solutions whose accuracy is comparable to that of the Cholesky factorization, while the conditioning measured by the effect of roundoff on polynomials in the L² norm is far less severe than the conditioning in the ordinary 2-norm.

What carries the argument

Explicit eigendecomposition of the univariate Bernstein mass matrix, constructible in O(n²) operations via exact formulae.

If this is right

  • Exact formulae give the entries of the inverse without iteration or recursion.
  • Hankel–Toeplitz–diagonal factorizations allow structured inversion without forming the inverse explicitly.
  • The O(n²) eigendecomposition produces linear-system solutions whose accuracy is comparable to Cholesky.
  • Conditioning measured in the L² norm induced on polynomials is far milder than the usual matrix 2-norm conditioning.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same structured factorizations may extend to mass matrices on higher-dimensional simplices once a suitable multivariate basis ordering is chosen.
  • Because the L²-norm conditioning is milder, Bernstein-based discretizations could remain stable at higher polynomial degrees than standard nodal bases when roundoff is the dominant error source.
  • The O(n²) spectral construction supplies an inexpensive way to obtain a well-conditioned basis change for any interval-based finite-element code that already stores Bernstein coefficients.

Load-bearing premise

The univariate Bernstein mass matrix possesses closed-form inverse entries and an explicit eigendecomposition that can be built with only O(n²) arithmetic operations.

What would settle it

A direct count of floating-point operations showing that any implementation of the claimed eigendecomposition requires more than quadratic work for some sequence of matrix sizes, or a numerical experiment in which the forward error of the spectral solver exceeds that of Cholesky by more than a small constant factor on a sequence of increasing n.

Figures

Figures reproduced from arXiv: 1907.05773 by Larray Allen, Robert C. Kirby.

Figure 1
Figure 1. Figure 1: Bernstein mass matrix conditioning for degrees 0 t [PITH_FULL_IMAGE:figures/full_fig_p014_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Plots of two functions being approximating with Be [PITH_FULL_IMAGE:figures/full_fig_p015_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Relative error/residual in using the methods desc [PITH_FULL_IMAGE:figures/full_fig_p016_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Relative error/residual in using the methods desc [PITH_FULL_IMAGE:figures/full_fig_p017_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Error/residual in using the methods described in S [PITH_FULL_IMAGE:figures/full_fig_p018_5.png] view at source ↗
read the original abstract

Bernstein polynomials, long a staple of approximation theory and computational geometry, have also increasingly become of interest in finite element methods. Many fundamental problems in interpolation and approximation give rise to interesting linear algebra questions. Previously, we gave block-structured algorithms for inverting the Bernstein mass matrix on simplicial cells, but did not study fast alorithms for the univariate case. Here, we give several approaches to inverting the univariate mass matrix based on exact formulae for the inverse; decompositions of the inverse in terms of Hankel, Toeplitz, and diagonal matrices; and a spectral decomposition. In particular, the eigendecomposition can be explicitly constructed in $\mathcal{O}(n^2)$ operations, while its accuracy for solving linear systems is comparable to that of the Cholesky decomposition. Moreover, we study conditioning and accuracy of these methods from the standpoint of the effect of roundoff error in the $L^2$ norm on polynomials, showing that the conditioning in this case is far less extreme than in the standard 2-norm.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript presents several structured approaches to inverting the univariate Bernstein mass matrix, including exact closed-form expressions for the inverse entries, decompositions of the inverse as products involving Hankel, Toeplitz, and diagonal matrices, and an explicit eigendecomposition. It asserts that this eigendecomposition can be constructed in O(n²) operations, that the resulting solvers achieve accuracy comparable to Cholesky factorization, and that conditioning measured via the effect of roundoff error in the L² norm on polynomials is substantially milder than the standard matrix 2-norm.

Significance. If the O(n²) construction and L²-norm conditioning claims hold with the stated accuracy, the work supplies practical, structure-exploiting tools for mass-matrix inversion in univariate finite-element and approximation settings that use Bernstein bases. The explicit spectral decomposition and the shift from 2-norm to L²-norm error analysis constitute clear strengths that could influence both theory and implementation in computational geometry and FEM codes.

major comments (2)
  1. [Abstract; spectral-decomposition section] Abstract and the section presenting the spectral decomposition: the central claim that the full eigendecomposition (n eigenvectors) can be populated in O(n²) arithmetic operations total is load-bearing for the paper’s complexity advantage. The skeptic concern is valid here; the manuscript must supply either (i) explicit per-entry formulae whose evaluation cost is O(1) after O(n) precomputation or (ii) a precise operation-count argument showing that any binomial or summation costs are amortized to O(1) per entry. Without this, the stated O(n²) bound cannot be verified and the comparison to Θ(n³) dense methods remains unsubstantiated.
  2. [Numerical results / conditioning analysis] Section on numerical experiments and conditioning: the assertion that accuracy is “comparable to that of the Cholesky decomposition” and that L²-norm conditioning is “far less extreme” requires quantitative support (e.g., tables of relative residuals or condition-number ratios versus n). If these comparisons rest only on a few small-n examples without an accompanying forward-error analysis in the L² inner-product norm, the claim is not yet load-bearing for the central contribution.
minor comments (2)
  1. [Introduction and notation section] The notation distinguishing the Bernstein mass matrix M from its inverse and from the various structured factors (Hankel, Toeplitz, diagonal) should be introduced once and used consistently; occasional reuse of the same symbol for different objects obscures the decomposition statements.
  2. A short table or pseudocode listing the exact arithmetic cost of each proposed inversion method (exact inverse, structured factorization, spectral) would help readers compare them directly.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and the constructive comments on our manuscript. We address each major comment below, indicating the revisions we will make to strengthen the presentation.

read point-by-point responses

  1. Referee: [Abstract; spectral-decomposition section] Abstract and the section presenting the spectral decomposition: the central claim that the full eigendecomposition (n eigenvectors) can be populated in O(n²) arithmetic operations total is load-bearing for the paper’s complexity advantage. The skeptic concern is valid here; the manuscript must supply either (i) explicit per-entry formulae whose evaluation cost is O(1) after O(n) precomputation or (ii) a precise operation-count argument showing that any binomial or summation costs are amortized to O(1) per entry. Without this, the stated O(n²) bound cannot be verified and the comparison to Θ(n³) dense methods remains unsubstantiated.

    Authors: We appreciate the referee’s emphasis on rigor for the complexity claim. The manuscript already supplies explicit per-entry formulae for the eigenvectors (involving binomial coefficients and a small number of auxiliary terms that are independent of the entry index once n is fixed). These admit direct O(1) evaluation per entry after an O(n) precomputation of the binomial coefficients (or their ratios). In the revised manuscript we will insert a short operation-count paragraph immediately after the formulae, enumerating the arithmetic operations per eigenvector entry and confirming that the total cost for all n eigenvectors is indeed O(n²). revision: yes

  2. Referee: [Numerical results / conditioning analysis] Section on numerical experiments and conditioning: the assertion that accuracy is “comparable to that of the Cholesky decomposition” and that L²-norm conditioning is “far less extreme” requires quantitative support (e.g., tables of relative residuals or condition-number ratios versus n). If these comparisons rest only on a few small-n examples without an accompanying forward-error analysis in the L² inner-product norm, the claim is not yet load-bearing for the central contribution.

    Authors: We agree that the numerical evidence must be made more quantitative to support the central claims. The existing experiments already include forward-error measurements in the L² norm on polynomials, but they are limited to small n. In the revision we will add a table (or expanded figure) reporting relative residuals and effective condition-number ratios versus n up to at least degree 30, together with a concise forward-error analysis that relates the observed L²-norm errors to the round-off model used in the paper. This will make the comparison with Cholesky and the milder L² conditioning fully load-bearing. revision: yes

Circularity Check

0 steps flagged

No circularity; derivations use exact formulae and standard decompositions

full rationale

The paper presents explicit formulae for the inverse of the univariate Bernstein mass matrix, structured decompositions (Hankel/Toeplitz/diagonal), and an eigendecomposition constructible in O(n²) operations. These rest on algebraic properties of Bernstein polynomials and classical matrix factorizations, with no reduction of any claimed prediction or result to a fitted parameter, self-definition, or load-bearing self-citation. The prior self-citation addresses only the multivariate case and is not invoked to justify the univariate claims. The derivation chain is self-contained against external benchmarks and does not match any enumerated circularity pattern.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work relies on established properties of Bernstein polynomials and linear algebra; no free parameters, invented entities, or ad-hoc assumptions are apparent from the abstract.

axioms (2)
  • domain assumption Bernstein polynomials of degree n form a basis for polynomials on [0,1] whose L2 inner products define the mass matrix entries via beta functions or binomial coefficients.
    Required to define the matrix and derive its inverse formulae.
  • standard math Standard results on Hankel, Toeplitz, and spectral decompositions of matrices apply to the inverse.
    Invoked to structure the inverse and construct the eigendecomposition.

pith-pipeline@v0.9.0 · 5699 in / 1392 out tokens · 31249 ms · 2026-05-24T22:23:27.956092+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

  1. [1]

    Be rnstein–B´ ezier finite elements of arbitrary order and optimal assembly procedures

    Mark Ainsworth, Gaelle Andriamaro, and Oleg Davydov. Be rnstein–B´ ezier finite elements of arbitrary order and optimal assembly procedures. SIAM Journal on Scientific Computing , 33(6):3087–3109, 2011

    work page 2011

  2. [2]

    Bernstein–B´ ezier base s for tetrahedral finite elements

    Mark Ainsworth and Guosheng Fu. Bernstein–B´ ezier base s for tetrahedral finite elements. Computer Methods in Applied Mechanics and Engineering , 340:178–201, 2018

    work page 2018

  3. [3]

    Sanch´ ez

    Mark Ainsworth, Shuai Jiang, and Manuel A. Sanch´ ez. An O(p3) hp-version FEM in two dimensions: Preconditioning and post-processing. Computer Methods in Applied Mechanics and Engineering , 350:766 – 802, 2019

    work page 2019

  4. [4]

    Arnold, Richard S

    Douglas N. Arnold, Richard S. Falk, and Ragnar Winther. G eometric decompositions and local bases for spaces of finite element differential forms. Computer Methods in Applied Mechanics and Engineering , 198(21-26):1660–1672, 2009

    work page 2009

  5. [5]

    D´ emonstration du th´ eor` eme de weier strass fond` ee sur le calcul des proba- bilit´ es.Communications de la Soci´ et´ e Math´ ematique de Kharkov, 13(1):1–2, 1912

    Serge Bernstein. D´ emonstration du th´ eor` eme de weier strass fond` ee sur le calcul des proba- bilit´ es.Communications de la Soci´ et´ e Math´ ematique de Kharkov, 13(1):1–2, 1912

    work page 1912

  6. [6]

    Quadrature over a pyramid or cube of integr ands with a singularity at a vertex

    Michael G Duffy. Quadrature over a pyramid or cube of integr ands with a singularity at a vertex. SIAM journal on Numerical Analysis , 19(6):1260–1262, 1982

    work page 1982

  7. [7]

    Rida T. Farouki. Legendre–Bernstein basis transformat ions. Journal of Computational and Applied Mathematics , 119(1-2):145–160, 2000

    work page 2000

  8. [8]

    Golub and Charles F

    Gene H. Golub and Charles F. Van Loan. Matrix computations, volume 3. JHU press, 2012

    work page 2012

  9. [9]

    Algebraic methods for Toeplitz-like matrices and operator s, volume 13

    Georg Heinig and Karla Rost. Algebraic methods for Toeplitz-like matrices and operator s, volume 13. Birkh¨ auser, 1984

    work page 1984

  10. [10]

    Robert C. Kirby. Fast simplicial finite element algorit hms using Bernstein polynomials. Nu- merische Mathematik , 117(4):631–652, 2011

    work page 2011

  11. [11]

    Robert C. Kirby. Low-complexity finite element algorit hms for the de Rham complex on simplices. SIAM Journal on Scientific Computing , 36(2):A846–A868, 2014

    work page 2014

  12. [12]

    Robert C. Kirby. Fast inversion of the simplicial Berns tein mass matrix. Numerische Mathe- matik, 135(1):73–95, 2017

    work page 2017

  13. [13]

    Kirby and Kieu Tri Thinh

    Robert C. Kirby and Kieu Tri Thinh. Fast simplicial quad rature-based finite element operators using Bernstein polynomials. Numerische Mathematik , 121(2):261–279, 2012

    work page 2012

  14. [14]

    B´ ezier representation of the constrained dual Bern- stein polynomials

    Stanis/suppress law Lewanowicz and Pawe/suppress l Wo´ zny. B´ ezier representation of the constrained dual Bern- stein polynomials. Applied Mathematics and Computation , 218(8):4580–4586, 2011

    work page 2011

  15. [15]

    Gram matrix of Bernstein basis: Properties and applications

    Lizheng Lu. Gram matrix of Bernstein basis: Properties and applications. Journal of Com- putational and Applied Mathematics , 280:37–41, 2015

    work page 2015

  16. [16]

    Luk and Sanzheng Qiao

    Franklin T. Luk and Sanzheng Qiao. A fast eigenvalue alg orithm for Hankel matrices. Linear Algebra and Its Applications , 316(1-3):171–182, 2000

    work page 2000

  17. [17]

    Linear algebra and its applications

    Gilbert Strang. Linear algebra and its applications . Thomson, 2006. 19

    work page 2006