Skip to content

Tiers 1 & 2: Structural-Property Generators for `mtl::generators`

MTL5 needs a test matrix generation facility analogous to MATLAB’s gallery() — matrices with known mathematical properties for verifying decompositions, solvers, and eigenvalue routines. Tier 1 provides implicit (storage-free) generators; Tier 2 provides factory functions returning concrete dense2D<T> or compressed2D<T>.

Tier 1 — Implicit generators are lightweight classes with operator()(r, c) that compute entries on-the-fly. They satisfy the Matrix concept without allocating storage. Each requires trait registration (category<> → tag::dense, ashape<> → mat<V>).

Tier 2 — Factory generators are free functions returning dense2D<T> or compressed2D<T>. No trait registration needed since they return concrete types.

GeneratorFormulaKey Properties
hilbert<T>(n)H(i,j) = 1/(i+j+1)SPD, notoriously ill-conditioned
lehmer<T>(n)L(i,j) = (min(i,j)+1)/(max(i,j)+1)SPD, well-conditioned, diag=1
lotkin<T>(n)Row 0 all 1s, rest = HilbertAsymmetric, ill-conditioned
ones<T>(n) / ones<T>(m,n)O(i,j) = 1Rank-1, supports rectangular
minij<T>(n)M(i,j) = min(i+1, j+1)SPD, known inverse

Tier 2: Dense Factory Generators (8 files)

Section titled “Tier 2: Dense Factory Generators (8 files)”
GeneratorFormulaKey Properties
kahan<T>(n, θ, pert)Upper triangular, K(i,i)=s^i+pert·ε·(n-i), K(i,j)=-c·s^iIll-conditioned, tests QR
frank<T>(n)F(i,j) = n+1-max(i+1,j+1) for j≥i-1Upper Hessenberg, known eigenvalues
moler<T>(n, α)M = L·L^T, L unit lower tri with off-diag αSPD, eigenvalues cluster near 0
pascal<T>(n)P(i,j) = C(i+j, i), recurrence P(i,j)=P(i-1,j)+P(i,j-1)SPD, det=1, binomial structure
clement<T>(n)C(i,i±1) = √((i+1)(n-1-i)), diag=0Tridiagonal symmetric, known eigenvalues
companion<T>(coeffs)Subdiag=1, last col=-coeffsEigenvalues = polynomial roots
vandermonde<T>(nodes)V(i,j) = nodes[i]^jIll-conditioned for uniform nodes
forsythe<T>(n, α, λ)Jordan block + corner perturbation F(n-1,0)=αTests near-defective matrices

Tier 2: Sparse Factory Generator (1 file, 2 functions)

Section titled “Tier 2: Sparse Factory Generator (1 file, 2 functions)”
GeneratorFormulaKey Properties
laplacian_1d<T>(n)Tridiagonal [-1, 2, -1]SPD sparse, known eigenvalues λ_k = 2-2cos(kπ/(n+1))
laplacian_2d<T>(nx, ny)5-point stencil, diag=4, neighbors=-1SPD sparse, (nx·ny)×(nx·ny), ≤5 nnz/row
include/mtl/generators/
hilbert.hpp ← implicit, SPD, ill-conditioned
lehmer.hpp ← implicit, SPD, well-conditioned
lotkin.hpp ← implicit, asymmetric, ill-conditioned
ones.hpp ← implicit, rank-1
minij.hpp ← implicit, SPD
kahan.hpp ← factory → dense2D, upper triangular
frank.hpp ← factory → dense2D, upper Hessenberg
moler.hpp ← factory → dense2D, SPD, L*L^T
pascal.hpp ← factory → dense2D, SPD, binomial
clement.hpp ← factory → dense2D, tridiagonal
companion.hpp ← factory → dense2D, polynomial roots
vandermonde.hpp ← factory → dense2D, ill-conditioned
forsythe.hpp ← factory → dense2D, near-defective
laplacian.hpp ← factory → compressed2D, 1D and 2D
generators.hpp ← umbrella header
tests/unit/generators/
test_hilbert.cpp
test_lehmer.cpp
test_lotkin.cpp
test_ones.cpp
test_minij.cpp
test_kahan.cpp
test_frank.cpp
test_moler.cpp
test_pascal.cpp
test_clement.cpp
test_companion.cpp
test_vandermonde.cpp
test_forsythe.cpp
test_laplacian.cpp
  • include/mtl/mtl_fwd.hpp — add forward declarations for the 5 implicit generator classes
  • tests/unit/CMakeLists.txt — add glob for generators/*.cpp via compile_all()
  • No changes needed for factory generators (they return concrete types, no forward declarations needed)

Each implicit generator follows this template:

namespace mtl::generators {
template <typename Value = double>
class hilbert {
public:
using value_type = Value;
using size_type = std::size_t;
explicit hilbert(size_type n) : n_(n) {}
value_type operator()(size_type r, size_type c) const {
return Value(1) / Value(r + c + 1);
}
size_type num_rows() const { return n_; }
size_type num_cols() const { return n_; }
size_type size() const { return n_ * n_; }
private:
size_type n_;
};
} // namespace mtl::generators

Required trait registrations (at bottom of each file):

namespace mtl::traits {
template <typename V>
struct category<generators::hilbert<V>> { using type = tag::dense; };
}
namespace mtl::ashape {
template <typename V>
struct ashape<::mtl::generators::hilbert<V>> { using type = mat<V>; };
}

Forward declarations in mtl_fwd.hpp:

namespace generators {
template <typename Value> class hilbert;
template <typename Value> class lehmer;
template <typename Value> class lotkin;
template <typename Value> class ones;
template <typename Value> class minij;
}
namespace mtl::generators {
template <typename T = double>
auto frank(std::size_t n) {
mat::dense2D<T> F(n, n);
for (std::size_t i = 0; i < n; ++i)
for (std::size_t j = 0; j < n; ++j) {
// compute F(i, j)
}
return F;
}
} // namespace mtl::generators
namespace mtl::generators {
template <typename T = double>
auto laplacian_1d(std::size_t n) {
mat::compressed2D<T> L(n, n);
{
mat::inserter<mat::compressed2D<T>> ins(L);
for (std::size_t i = 0; i < n; ++i) {
ins[i][i] << T(2);
if (i > 0) ins[i][i - 1] << T(-1);
if (i + 1 < n) ins[i][i + 1] << T(-1);
}
}
return L;
}
} // namespace mtl::generators

SPD. Condition number grows super-exponentially with n.

lehmer<T>(n) — L(i,j) = (min(i,j)+1)/(max(i,j)+1)

Section titled “lehmer<T>(n) — L(i,j) = (min(i,j)+1)/(max(i,j)+1)”

SPD. All diagonal entries = 1. All entries in (0, 1].

lotkin<T>(n) — First row all 1s, rest = Hilbert

Section titled “lotkin<T>(n) — First row all 1s, rest = Hilbert”

Asymmetric: L(0,1)=1 ≠ L(1,0)=0.5. Ill-conditioned like Hilbert.

ones<T>(n) / ones<T>(m,n) — All entries = 1

Section titled “ones<T>(n) / ones<T>(m,n) — All entries = 1”

Two constructors: square and rectangular. Rank-1 matrix.

SPD. For 3×3: [[1,1,1],[1,2,2],[1,2,3]].

kahan<T>(n, θ=1.2, pert=25) — Upper triangular

Section titled “kahan<T>(n, θ=1.2, pert=25) — Upper triangular”

As MATLAB’s gallery('kahan', n, theta, pert): K = diag(1, s, …, s^(n-1)) · (I − c·triu(ones(n), 1)) + pert·ε·diag(n, n-1, …, 1).

  • s = sin(θ), c = cos(θ), ε = std::numeric_limits<T>::epsilon()
  • K(i,i) = s^i + pert·ε·(n-i)
  • K(i,j) = -c · s^i for j > i
  • K(i,j) = 0 for j < i
  • The condition number grows exponentially in n: κ₁ ≈ 92 for n = 10 and 2.9e5 for n = 30 (θ = 1.2).
  • The small perturbation keeps column-pivoted QR from swapping columns that tie only through rounding. With pert = 0 you get the unperturbed matrix.
  • Before #844 the diagonal was s^i · 25. That scaling made the matrix well conditioned (κ₁ = 2.1 for n = 10).
  • F(i,j) = n+1-max(i+1,j+1) for j ≥ i-1, else 0
  • For n=4: [[4,3,2,1],[3,3,2,1],[0,2,2,1],[0,0,1,1]]
  • Subdiagonal: F(i,i-1) = n-i
  • L = unit lower triangular with L(i,j) = α for i > j
  • M(i,i) = i·α² + 1
  • M(i,j) = min(i,j)·α² + α for i ≠ j
  • For α=-1, n=3: [[1,-1,-1],[-1,2,0],[-1,0,3]]
  • P(i,0) = P(0,j) = 1
  • P(i,j) = P(i-1,j) + P(i,j-1)
  • Entries are C(i+j, i), which grow like 4^n. They are exact in float up to n = 14 and in double up to n = 29. The largest entry overflows to inf in float for n ≥ 67, and in double for n ≥ 516.

clement<T>(n) — Tridiagonal, known eigenvalues

Section titled “clement<T>(n) — Tridiagonal, known eigenvalues”
  • Diagonal = 0
  • C(i,i±1) = √((i+1)(n-1-i))
  • Eigenvalues: n-1, n-3, …, -(n-1). That is ±(n-1), …, ±1 for even n, and ±(n-1), …, ±2, 0 for odd n.

companion<T>(coeffs) — Polynomial eigenvalue matrix

Section titled “companion<T>(coeffs) — Polynomial eigenvalue matrix”
  • Input: coefficients [c₀, c₁, …, c_{n-1}] of p(x) = x^n + c_{n-1}x^{n-1} + … + c₀
  • Subdiagonal = 1, last column = -coeffs, rest = 0
  • Eigenvalues = roots of p(x)

vandermonde<T>(nodes) — V(i,j) = nodes[i]^j

Section titled “vandermonde<T>(nodes) — V(i,j) = nodes[i]^j”
  • First column all 1s
  • Ill-conditioned for uniformly-spaced nodes

forsythe<T>(n, α=1e-10, λ=0) — Perturbed Jordan block

Section titled “forsythe<T>(n, α=1e-10, λ=0) — Perturbed Jordan block”
  • Diagonal = λ, superdiagonal = 1, F(n-1,0) = α
  • Eigenvalues for n ≥ 2: λ + α^(1/n) times the n-th roots of unity
  • When α=0: pure Jordan block
  • For n = 1 the corner is the diagonal, so the result is [λ]. MATLAB gives [α].
  • Tests eigensolvers near defective matrices

laplacian_1d<T>(n) — 1D discrete Laplacian

Section titled “laplacian_1d<T>(n) — 1D discrete Laplacian”
  • Tridiagonal: [-1, 2, -1]
  • SPD. Eigenvalues: 2 - 2cos(kπ/(n+1))

laplacian_2d<T>(nx, ny) — 2D discrete Laplacian

Section titled “laplacian_2d<T>(nx, ny) — 2D discrete Laplacian”
  • 5-point stencil on nx×ny grid → (nx·ny)×(nx·ny) sparse matrix
  • Diagonal = 4, off-diagonal neighbors = -1

All tests use Catch2 with WithinAbs floating-point matchers.

TestKey Verifications
test_hilbertConcept check, H(i,j)=1/(i+j+1), symmetry, condition growth
test_lehmerConcept check, L(i,j) formula, symmetry, diagonal=1, positivity
test_lotkinConcept check, first row=1, rows 1+ match Hilbert, asymmetry
test_onesConcept check, square/rectangular, all entries=1, integer type
test_minijConcept check, M(i,j)=min(i+1,j+1), symmetry, known 3×3
test_kahanDimensions, upper triangular, diagonal=s^i, superdiag=-c·s^i; κ₁ against the closed-form inverse in test_generator_properties
test_frankDimensions, Hessenberg, known 4×4, subdiag=n-i
test_molerDimensions, symmetry, known 3×3, L·L^T reconstruction, custom α
test_pascalDimensions, symmetry, known values, first row/col=1, recurrence
test_clementDimensions, tridiagonal, diag=0, symmetry, known 4×4 values
test_companionDimensions, subdiag=1, last col=-coeffs, 2×2 quadratic roots
test_vandermondeDimensions, V(i,j)=nodes[i]^j, first col=1, second col=nodes
test_forsytheDimensions, diag=λ, superdiag=1, corner=α, zero-α Jordan
test_laplacian1D: tridiag [-1,2,-1], row sums; 2D: dimensions, diag=4, symmetry
  1. Implicit generators (hilbert, lehmer, lotkin, ones, minij) + trait registrations + forward declarations + tests
  2. Dense factory generators (kahan, frank, moler, pascal, clement, companion, vandermonde, forsythe) + tests
  3. Sparse factory generator (laplacian) + test
  4. Umbrella header generators.hpp
  5. CMakeLists.txt test registration
  6. Full build + full test suite
Terminal window
cd /home/stillwater/dev/stillwater/clones/mtl5
cmake -B build
cmake --build build -j$(nproc)
ctest --test-dir build # all tests pass
ctest --test-dir build -R generators # generator tests specifically