CS Paper Radar

A note on the rectangular Schoenberg-Whitney theorem for clamped B-splines

Shutao Tang, Zixuan Zhao

cs.GR math.NA ·submitted 2026-10-17 03:42 UTC · v1
theory

Abstract

Wang et al.(Computer-Aided Design 40 (2008) 999-1008) proposed a knot-subsequence characterization of full row rank for rectangular B-spline collocation matrices. We identify an incorrect inequality in their Appendix proof, which invalidates the argument as written, and make explicit the endpoint and multiplicity conventions on which the criterion depends. The defect lies in the proof, not in the underlying result, which is valid under suitably stated hypotheses; in the lofting construction of Wang et al. these hypotheses are implicitly satisfied, so the lofted curves are unaffected. We state the corrected result and give a new proof, independent of the disputed argument, for clamped B-splines of arbitrary degree with continuous interior multiplicities. In our proof, sufficiency follows from inclusion of spline spaces and knot insertion; necessity selects independent columns and builds the reduced knot vector from them. The proof uses no recursive column-selection construction.

Comment
7 pages, 1 figure

Closest papers

Nearest neighbours by meaning across the whole index.

Energy-minimized interpolatory B-spline lofting for sequences of closed contours

cs.GR math.NA ·2026-10-17 ·Shutao Tang, Zixuan Zhao
similarity 0.71
Abstract · 19 pages, 9 figures

B-spline lofting through closed cross-sections is common in reverse engineering, but interpolating each section on its own knot vector can produce an unnecessarily large control net. We construct a common-knot method for closed section curves of odd and even degree by minimizing the strain energy of each section subject to its interpolation constraints. Feasibility for closed section data and uniqueness of the resulting saddle-point solution require full row rank of the periodic collocation matrices, a property that a previously proposed periodic Schoenberg-Whitney window condition does not always guarantee. We establish the exact parity distinction: the condition is sufficient at odd point counts but admits singular configurations at every admissible even point count. For the odd and even degrees used here, the natural and shifting anchor knots are nonsingular; at odd point counts the window condition certifies the selected candidate, whereas at even point counts a rank test with an anchor fallback is applied. The lofting method therefore retains a nonsingular square subsystem for each section and uses nestedness to transfer full row rank to the rectangular common-knot system. Across six closed-contour models the common-knot method uses 83-98% fewer control points than traditional interpolating lofting, with section energies no larger than those of a previous knot-selection method within numerical precision.

0.29

Combinatorial maps for hierarchical splines

cs.CG ·2026-08-30 ·Caleb B. Goates, Kendrick M. Shepherd, Derek C. Thomas
similarity 0.58
Abstract

Hierarchical splines are an important part of multiscale and adaptive isogeometric analysis formulations. The Bézier meshes of these splines are an essential part of their definition and of several important hierarchical spline algorithms, such as adaptive refinement and Bézier extraction. Topological data associated with the Bézier mesh-such as adjacency information-can be used to improve the performance of many of these algorithms as well as downstream applications of the splines, but typical hierarchical spline formulations do not compute the topological data, storing instead just a list of elements. In this work we present algorithms to build a performant topological data structure, namely the combinatorial map, to represent Bézier meshes of hierarchical splines over cubical cell complexes where the refinement levels have conforming Bézier meshes. This includes hierarchical and truncated hierarchical B-splines, as well as subsets of other hierarchical spline formulations. We show the performance characteristics of the construction algorithms of these hierarchical combinatorial maps, as well as an example use case, showing that the topological information can provide up to an order of magnitude reduction in computation time in downstream applications of the splines.

0.24

Hybrid Reconstruction of Admissible Spline Spaces from Locally Modified Unclamped Patches for Isogeometric Analysis

cs.GR ·2026-09-14 ·C. G. Provatidis, I. Dimitriou
similarity 0.56
Abstract · 76 pages, 13 figures

We propose a decoupled reconstruction framework that temporarily decomposes a NURBS representation into independent local Active Sections, enabling arbitrary local knot insertion, degree elevation, and basis modifications while preserving exact CAD geometry. However, these independent modifications inevitably violate inter-patch continuity, requiring a robust algebraic recovery of global admissibility. We introduce a novel reconstruction methodology that constructs a positive Hybrid Reconstruction Operator: anchor degrees of freedom are identified via QR pivoting, after which a sequence of linear programming problems with distance-based regularization generates strictly non-negative nullspace vectors, while a subsequent non-negative least-squares solve enforces a precise partition of unity. Crucially, to ensure computational efficiency and preserve locality, we implement a hierarchical pairwise condensation strategy that freezes columns already satisfying new interface constraints, confining the optimization exclusively to the active degrees of freedom at each merge step. The resulting hybrid basis is, by construction, strictly non-negative, spans the exact constrained nullspace, preserves partition of unity to machine precision, and reproduces the original geometry exactly. Numerical benchmarks, including a nonlinear diffusion problem on multi-patch curves with heterogeneous local polynomial degrees, confirm optimal convergence rates and demonstrate the framework's ability to seamlessly combine local geometric flexibility with globally consistent approximation spaces. By entirely decoupling local spline editing from the enforcement of continuity, this methodology provides a highly efficient, mathematically principled, and universally applicable tool for adaptive Isogeometric Analysis.

0.32

InKAN: B-Spline KANs via Truncated Power Form

cs.LG math.NA ·2026-09-02 ·Naveen Mysore
code/data similarity 0.53
Abstract · Open-source implementation: pip install inkan, experiments (speed, classification, regression), 8 Pages

Kolmogorov-Arnold Networks (KANs) place learnable B-spline activations on network edges rather than fixed activations on nodes. The standard Cox-de Boor recursion evaluates these activations through $k$ sequential passes for degree-$k$ splines, consuming over 90% of forward-pass time. InKAN replaces this recursion with the truncated power form, a classical result from approximation theory that expresses each uniform cubic B-spline as five $(x)_+^3$ terms at shifted knot positions. The resulting expression computes exact B-spline basis values: the same mathematical function as the Cox-de Boor recursion, evaluated without sequential passes. This paper documents three contributions: (1) an implementation structured for torch . compile fusion, eliminating recursion, span lookup, and scatter-gather operations; (2) a bounded-coordinate evaluation that clamps the normalized input to $[0, k{+}1]$, preventing the growth of cancellation error at large off-support coordinates; and (3) an open-source package (pip install inkan). In the tested configurations, InKAN has 2.8--3.5$\times$ lower forward-pass latency than the Cox-de Boor recursion. Partition-of-unity errors remain below $10^{-5}$ for grid sizes up to 200.

0.69

Computing distances in braid-move graphs, higher Bruhat orders, and oriented-matroid mutation graphs is NP-hard

cs.DM math.CO ·2026-10-01 ·Tilen Marc
theorycode/data similarity 0.45
Abstract · 33 pages, 5 figures. v2: restructured and several proofs shortened. Code, computational checks and Lean formalization: https://github.com/ti…

A wiring diagram is an arrangement of $m$ pseudolines, every two of which cross exactly once. Reading its crossings from left to right encodes it as a reduced word of the permutation $w_0\in S_m$ that reverses $1,\dots,m$, unique up to commutations, and a braid move $σ_iσ_{i+1}σ_i\leftrightarrowσ_{i+1}σ_iσ_{i+1}$ flips one of its triangles. We prove that deciding whether two wiring diagrams are within a given braid-move distance is NP-complete. Equivalently, deciding flip distance is NP-complete in the higher Bruhat order $B(m,2)$, for triangle flips of marked arrangements of pseudolines, and for rhombic tilings of a $2m$-gon; this answers an open question on flip graphs of pseudoline arrangements (SODA 2024). The reduction is from Vertex Cover: for every graph $G$ we construct two wiring diagrams at braid-move distance $|D|+2\operatorname{VC}(G)$, where $\operatorname{VC}(G)$ is the vertex cover number of $G$ and the Hamming distance $|D|$ is the number of triples of wires whose triangles are oriented differently. The construction glues copies of a seven-wire gadget whose braid-move distance exceeds its Hamming distance by $2$. Adding a line at infinity transfers the construction to rank-$3$ uniform oriented matroids, where two oriented matroids are adjacent in the mutation graph if their chirotopes differ in one basis; so deciding distance in the mutation graph is NP-complete in rank $3$. An iterate of Rambau's expansion of signotopes amplifies the excess and gives NP-hardness in every fixed rank $r\ge4$, and by duality in every fixed corank at least $3$. The same instances show that flip distance in the higher Bruhat orders $B(n,k)$ is NP-complete for every fixed $k\ge2$.

0.67

On the Binary Rank of Matrices with Constant Real Rank

cs.DM math.CO ·2026-09-24 ·Michal Parnas
theory similarity 0.45
Abstract

We study the problem of determining upper bounds on the maximal binary rank, $b_d$, of a $0,1$ matrix with real rank $d$, for small constant $d$. We prove a general upper bound of $b_d \leq \left\lfloor \sqrt{d2^d + 2d}\right\rfloor -1$. We also develop a general dimension reduction technique of bounding $b_d$ using known upper bounds on $b_{d-1}$ and $b_{d-2}$, as well as prove interesting general structural results on extremal matrices with binary rank $b_d$. This allows us to get improved non-trivial upper bounds on $b_d$ for constant values of $d$, which imply tight bounds on $b_d$ for $3 \leq d \leq 5$. Our results also imply bounds on the equivalent problem of finding the minimum number of bicliques needed to partition the edges of a bipartite graph whose reduced adjacency matrix has real rank at most $d$.

0.12

Chordal Construction of Column-Twisted Reed--Solomon Codes

cs.IT ·2026-10-22 ·Anuj Kumar Bhagat, Krishna Kaipa
hot direction similarity 0.44
Abstract

A $[n,k]_q$ Generalized Reed--Solomon (GRS) code can be represented, up to monomial equivalence, by a projective system consisting of $n$ points on a degree $(k-1)$ rational normal curve (RNC) $C_{k-1}$ in PG$(k-1,q)$. We use the term \textit{Column-Twisted Reed--Solomon (CTRS)} codes broadly for $[n,k]_q$ codes whose projective system contains at least $(k+2)$ points on a $C_{k-1}$ of PG$(k-1,q)$. By a chord of $C_{k-1}$, we mean a line which is either a tangent, a real secant, or an imaginary secant of $C_{k-1}$. Roth and Lempel constructed non-GRS MDS $[n,k]_q$ codes by considering projective systems consisting of $(n-1)$ points on $C_{k-1}$ together with a point on a tangent line. More recently, Liu et al. obtained non-GRS $[n, k]_q$ MDS codes by considering projective systems consisting of $(n-2)$ points on $C_{k-1}$ together with a pair of points on a real secant. In the case when $q$ is odd, the length of these codes satisfies $k+4 \leq n \leq (q+3)/2$. In this article, we construct non-GRS $[n,k]_q$ MDS codes by considering projective systems consisting of $(n-2)$ points on $C_{k-1}$ together with a pair of Galois conjugate points on an imaginary secant. For odd $q$, these codes have lengths satisfying $k+4 \le n\le (q+5)/2$, thereby improving both the attainable lengths and dimension ranges of previous TRS and CTRS constructions. In particular, our code attains the length $(q+5)/2$ for every $3\le k\le (q-3)/2$. We use a geometric argument to establish the non-GRS property of CTRS codes for the range $3\le k \le n-4$, while the traditional method of comparison with the Schur square of GRS codes proves the non-GRS property only for the narrower range $3\le k \le n/2$. We also determine the structure of the dual of any CTRS code.

0.47

The sum-of-squares complexity of linear-algebraic principles

cs.CC ·2026-11-03 ·Dmitriy Kunisky, Xifan Yu
similarity 0.44
Abstract · 41 pages

We study the degree needed for sum-of-squares (SoS) proofs of several basic principles of real linear algebra. For any $n\times n$ matrix $A$ of rank greater than $r$, the Weak Rank Principle states that the equations $XY^\top=A$ with $n\times r$ matrix variables $X, Y$ have no solution. We show that this principle requires degree exactly $2r+2$ to prove. On the other hand, for $A=I_n$, setting $X = Y$ gives the Tight Frame Principle, which has a degree-$4$ proof. For $n\times n$ matrices, proving that a right inverse is also a left inverse requires degree exactly $2n+2$, while proving that orthonormal rows imply orthonormal columns again has a degree-4 proof. Using our lower bounds, we also derive related SoS degree lower bounds for polynomial systems encoding sign rank, matrix rigidity, small-width homogeneous non-commutative algebraic branching programs, and tensor CP rank. Lastly, we show that quantitative bounds on the Frobenius norms of the factors in the Weak Rank Principle can lower the degree required to refute $XY^\top=I_n$, but sufficiently large bounds still preserve the exact degree $2r+2$ from the unbounded case, giving a quantitative version of the Archimedean property arising in classical results on SoS proofs.

0.28