═══════════════════════════════════════════════════════════════════════════════
ARB4J ISSUE — MATRIX-DSL EXTENSION TO THE EXPRESSION LANGUAGE
Block construction · structured forms · decomposition · slicing
═══════════════════════════════════════════════════════════════════════════════
§0 MOTIVATION
───────────────────────────────────────────────────────────────────────────────
The existing compiler already dispatches + − · ^ over ℝᵐˣⁿ and ℂᵐˣⁿ to
arb_mat_* / acb_mat_* via the codomain-chooses-the-algebra rule. What is
missing is *expression-level construction and decomposition* of structured
matrices — block assembly, partition, Kronecker / direct-sum / Hadamard,
adjoint glyphs, slicing, and named patterned-matrix constructors (Toeplitz,
Hankel, Vandermonde, companion, Jordan, Householder, Givens, …).
The pipeline does not need to change. Every item below is one of three
additions: a new BinaryOperationNode subclass, a new postfix unary node, or
a new construction node modelled on VectorNode.
═══════════════════════════════════════════════════════════════════════════════
§1 BLOCK LITERAL ⟦ … ⟧
───────────────────────────────────────────────────────────────────────────────
Extend the [ … ] vector-literal node with a 2-D block grid:
M ≔ ⟦ A │ B ;
C │ D ⟧ ── 2×2 block matrix
M ≔ ⟦ A │ B │ 𝟎 ;
𝟎 │ D │ E ;
F │ 𝟎 │ G ⟧ ── 3×3 block matrix, sparse cells
Type rule
∀ cell ∈ Mat(R) ∨ cell ∈ R (scalar promotes to 1×1 block)
block-row heights agree; block-column widths agree
empty cell ⇒ 𝟎-block of inferred shape
Codegen
acb_mat_init on the flattened shape, followed by per-block
acb_mat_window writes (zero-copy in Arb).
═══════════════════════════════════════════════════════════════════════════════
§2 BLOCK-INDEXED FOLDS (matrix analogue of Σ {k=a..b})
───────────────────────────────────────────────────────────────────────────────
Generalise the existing {k = a..b} binder to a tuple of indices:
M ≔ ⟦ A(i,j) {i = 1..p, j = 1..q} ⟧ ── block matrix
T ≔ ⟦ a(i,j) {i = 1..n, j = 1..n} ⟧ ── ordinary matrix
The codomain decides whether the cells are scalar or themselves matrices
(yielding a flattened block matrix at codegen).
═══════════════════════════════════════════════════════════════════════════════
§3 NEW BINARY OPERATORS (BinaryOperationNode subclasses)
───────────────────────────────────────────────────────────────────────────────
┌──────────────┬──────┬───────────┬───────────────────────────────┐
│ Operator │ Glyph│ ASCII │ Semantics │
├──────────────┼──────┼───────────┼───────────────────────────────┤
│ Direct sum │ ⊕ │ dsum │ block-diag(A, B) │
│ Kronecker │ ⊗ │ kron │ A ⊗ B, size (mp)×(nq) │
│ Hadamard │ ⊙ │ hadamard │ entry-wise A .* B │
│ Khatri–Rao │ ⊙ₖᵣ │ khatrirao │ column-wise Kronecker │
│ Composition │ ∘ │ compose │ T ∘ S ≡ T·S as morphisms │
└──────────────┴──────┴───────────┴───────────────────────────────┘
Each adds a row to BinaryOperationNode.initializeTypeMaps and emits
INVOKEVIRTUAL into the corresponding acb_mat_* primitive.
═══════════════════════════════════════════════════════════════════════════════
§4 POSTFIX UNARY DECORATORS (modelled on ! !! ⌊⌋ ⌈⌉ |·| x⁻¹)
───────────────────────────────────────────────────────────────────────────────
┌────────┬──────────────────────────┬────────────────────────────┐
│ Glyph │ Meaning │ Backend │
├────────┼──────────────────────────┼────────────────────────────┤
│ Aᵀ │ transpose │ acb_mat_transpose │
│ Aᴴ │ conjugate transpose │ acb_mat_conjugate_transpose│
│ A̅ │ entry-wise conjugate │ acb_mat_conjugate │
│ A⁻¹ │ inverse (already pow⁻¹) │ acb_mat_inv │
│ A⁺ │ Moore–Penrose pseudoinv │ SVD-based │
│ A^½ │ principal square root │ Schur-based │
│ A^k │ integer power │ repeated acb_mat_mul │
└────────┴──────────────────────────┴────────────────────────────┘
The Unicode-superscript path already in parseSuperscripts handles Aᵀ Aᴴ A⁺.
═══════════════════════════════════════════════════════════════════════════════
§5 SLICING & PROJECTION (the dual of construction)
───────────────────────────────────────────────────────────────────────────────
A[i, j] entry Scalar(R)
A[i₁ ‥ i₂, j₁ ‥ j₂] contiguous submatrix acb_mat_window
A[ : , j] column j Vec(R)
A[i , : ] row i Vec(R)
A[ℐ, 𝒥] gather by index vectors loop
diag(A) principal diagonal Vec(R)
diag(v) diagonal matrix from v Mat(R)
tril(A) triu(A) triangular parts acb_mat_*
tridiag(a,b,c) from sub/main/super diagonals
antidiag(A) secondary diagonal Vec(R)
═══════════════════════════════════════════════════════════════════════════════
§6 NAMED PATTERNED-MATRIX CONSTRUCTORS
───────────────────────────────────────────────────────────────────────────────
First-class function nodes, alongside Γ ζ Beta pFq ℰ :
Toeplitz(c, r) first column c, first row r
Hankel(c, r) antidiagonal-constant ◀ priority
Vandermonde(x, n) [ xᵢʲ ]
Companion(p) companion matrix of polynomial p
Jordan(λ, k) Jordan block J_k(λ)
Householder(v) I − 2 v vᴴ / (vᴴv)
Givens(i, j, θ) plane rotation Gᵢⱼ(θ)
Permutation(σ) from permutation vector
Diagonal(v) ≡ diag(v)
Circulant(c) cyclic shift of first column
Cauchy(x, y) [ 1/(xᵢ − yⱼ) ]
Pascal(n) binomial-coefficient matrix
DFT(n) n×n discrete-Fourier matrix
𝐈ₙ 𝟎ₘ,ₙ 𝟏ₘ,ₙ identity, zero, all-ones
The Hankel constructor is the leveraged primitive for the existing
spectral-recovery / Müntz–Padé / BFGS-Hankel-approximation work — it
removes the current need to drop into Java for coefficient packing.
═══════════════════════════════════════════════════════════════════════════════
§7 DECOMPOSITIONS AS MULTI-VALUED RETURNS
───────────────────────────────────────────────────────────────────────────────
Extend VectorNode to allow named destructuring:
⟨Q, R⟩ ≔ qr(A) A = QR
⟨L, U, P⟩ ≔ lu(A) PA = LU
⟨U, Σ, V⟩ ≔ svd(A) A = UΣVᴴ
⟨D, P⟩ ≔ eig(A) A = PDP⁻¹
⟨T, Q⟩ ≔ schur(A) A = QTQᴴ
⟨L⟩ ≔ chol(A) A = LLᴴ
⟨H, Q⟩ ≔ hessenberg(A) A = QHQᴴ
⟨P, L, U⟩ ≔ plu(A)
⟨B, U, V⟩ ≔ bidiag(A)
Type rule : each name binds to the corresponding component type.
Optimiser : if only one component of the tuple is used downstream, the
other components are not materialised.
═══════════════════════════════════════════════════════════════════════════════
§8 BILINEAR · QUADRATIC · NORMS · INVARIANTS
───────────────────────────────────────────────────────────────────────────────
xᵀ A y bilinear form Scalar
xᴴ A x Hermitian / quadratic form Scalar
‖x‖_A ≡ √( xᴴ A x ) A-norm Scalar
‖A‖_F Frobenius norm
‖A‖₂ ‖A‖∞ ‖A‖₁ operator norms
‖A‖_* nuclear (trace) norm
tr(A) det(A) acb_mat_trace, acb_mat_det
rank(A) numerical rank (with tol)
null(A) right null-space basis
range(A) column-space basis
cond(A) condition number
spec(A) spectrum (≡ eigenvalues vector)
ρ(A) spectral radius
═══════════════════════════════════════════════════════════════════════════════
§9 BLOCK-STRUCTURED n-ARY FOLDS (NAryOperationNode generalisation)
───────────────────────────────────────────────────────────────────────────────
Reuse the existing fold template; only identity + pairwise op change.
⨁ A(k) {k = 1..n} direct-sum fold
identity = empty matrix, op = ⊕
⨂ A(k) {k = 1..n} Kronecker-product fold
identity = [ppl-ai-file-upload.s3.amazonaws](https://ppl-ai-file-upload.s3.amazonaws.com/web/direct-files/attachments/991185483/9965c37e-fcb3-4aa9-b309-2b31f6a6354f/paste.txt) (1×1), op = ⊗
⊙ⱼ A(k) {k = 1..n} Hadamard-product fold
identity = 𝟏ₘ,ₙ, op = ⊙
The existing Σ and Π already work on matrix codomains for free via the
codomain rule.
═══════════════════════════════════════════════════════════════════════════════
§10 COMPOSITIONAL OPERATORS ON LINEAR MAPS
───────────────────────────────────────────────────────────────────────────────
For matrices viewed as morphisms in 𝐕𝐞𝐜𝐭(R):
T ∘ S composition ( = T·S )
T ⊗ S tensor product of maps
T ⊕ S direct sum of maps
T ↾ V restriction to subspace V (column space)
T / V quotient by invariant subspace
T* adjoint ( ≡ Tᴴ when V is finite-dim Hilbert)
Disambiguation : use ⊙ for Hadamard so ∘ remains composition,
matching the standard categorical reading.
═══════════════════════════════════════════════════════════════════════════════
§11 MATRIX-VALUED CALCULUS (free via existing differentiate / integral)
───────────────────────────────────────────────────────────────────────────────
The AST already carries ∂ and ∫ recursively; they extend at no extra
cost to matrix-valued expressions:
∂ₓ M(x) entry-wise derivative
∫ M(x) dx entry-wise integral
exp(A) acb_mat_exp ◀ already in Arb
log(A) matrix logarithm
sin(A) cos(A) analytic functional calc via Schur
f(A) general analytic functional calculus
Đ^α M(x) Caputo entry-wise
═══════════════════════════════════════════════════════════════════════════════
§12 GRAMMAR & AST IMPACT (summary)
───────────────────────────────────────────────────────────────────────────────
NEW BINARY NODES : KroneckerProductNode, DirectSumNode,
HadamardProductNode, KhatriRaoNode,
CompositionNode
NEW POSTFIX NODES : TransposeNode, AdjointNode, ConjugateNode,
PseudoInverseNode, MatrixSqrtNode
NEW CONSTRUCTION NODES : BlockMatrixNode, SliceNode, GatherNode,
ToeplitzNode, HankelNode, VandermondeNode,
CompanionNode, JordanNode, HouseholderNode,
GivensNode, PermutationNode,
CirculantNode, CauchyNode, DFTMatrixNode,
IdentityNode, ZeroMatrixNode, OnesMatrixNode
NEW NARY NODES : DirectSumFoldNode, KroneckerFoldNode,
HadamardFoldNode
NEW DESTRUCTURING : extend VectorNode ⟨a, b, c⟩ ≔ rhs
TYPE-TABLE ADDITIONS : (Mat, Mat) → Mat for ⊕ ⊗ ⊙
(Mat,) → Mat for ᵀ ᴴ ⁺ ̅
(Mat, Vec) → Vec for A·v
(Vec, Mat) → Vec for vᵀ·A
═══════════════════════════════════════════════════════════════════════════════
§13 PRIORITY ORDER (highest leverage first)
───────────────────────────────────────────────────────────────────────────────
① ⟦ A │ B ; C │ D ⟧ block literal
② Hankel(c, r) Toeplitz(c, r) Vandermonde(x, n) Companion(p)
③ Aᵀ Aᴴ A̅ postfix decorators
④ ⊗ ⊕ ⊙ new binary operators
⑤ A[i₁‥i₂, j₁‥j₂] diag(·) slicing & diagonal
⑥ ⟨Q, R⟩ ≔ qr(A) ⟨U,Σ,V⟩ ≔ svd(A) destructuring
⑦ ⨁ ⨂ folds
⑧ norms · invariants · matrix functional calculus
═══════════════════════════════════════════════════════════════════════════════
§14 ACCEPTANCE CRITERIA
───────────────────────────────────────────────────────────────────────────────
□ ⟦ A │ B ; C │ D ⟧ parses, typechecks, evaluates against acb_mat
□ Hankel(c, r) produces an acb_mat with the documented entry rule and
round-trips through svd + ⟨U,Σ,V⟩ destructuring
□ Aᵀ Aᴴ parse as postfix superscripts and dispatch to the correct
acb_mat_* primitive
□ A ⊗ B , A ⊕ B , A ⊙ B added to type table and round-trip-tested
□ ⨁ A(k) {k=1..n} and ⨂ A(k) {k=1..n} fold via NAryOperationNode
□ ‖x‖_A , tr(A) , det(A) , ρ(A) produce arbitrary-precision balls
□ exp(A) , log(A) , ∂ₓ M(x) succeed entry-wise
□ No regression in the existing scalar / polynomial / sequence pipelines
═══════════════════════════════════════════════════════════════════════════════
