Karl B. Hoffmann

M. Hecht, B. L. Cheeseman, K. B. Hoffmann et al.

For $m,n \in \mathbb{N}$, $m\geq 1$ and a given function $f : \mathbb{R}^m\longrightarrow \mathbb{R}$ the polynomial interpolation problem (PIP) is to determine a \emph{generic node set} $P \subseteq \mathbb{R}^m$ and the coefficients of the uniquely defined polynomial $Q\in\mathbb{R}[x_1,\dots,x_m]$ in $m$ variables of degree $\mathrm{deg}(Q)\leq n \in \mathbb{N}$ that fits $f$ on $P$, i.e., $Q(p) = f(p)$, $\forall\, p \in P$. We here show that in general, i.e., for arbitrary $m,n \in \mathbb{N}$, $m \geq 1$, there exists an algorithm that determines $P$ and computes the $N(\mbox{m,n})=\#P$ coefficients of $Q$ in $\mathcal{O}\big(N(\mbox{m,n})^2\big)$ time using $\mathcal{O}\big(\mbox{m}N(\mbox{m,n})\big)$ storage, without inverting the occurring Vandermonde matrix. We provide such an algorithm, termed PIP-SOLVER, based on a recursive decomposition of the problem and prove its correctness. Since the present approach solves the PIP without matrix inversion, it is computationally more efficient and numerically more robust than previous approaches. We demonstrate this in numerical experiments and compare with previous approaches based on matrix inversion and linear systems solving.

Karl B. Hoffmann, Ivo F. Sbalzarini

The identification of singular points or topological defects in discretized vector fields occurs in diverse areas ranging from the polarization of the cosmic microwave background to liquid crystals to fingerprint recognition and bio-medical imaging. Due to their discrete nature, defects and their topological charge cannot depend continuously on each single vector, but they discontinuously change as soon as a vector changes by more than a threshold. Considering this threshold of admissible change at the level of vectors, we develop a robustness measure for discrete defect estimators. Here, we compare different template paths for defect estimation in discretized vector or orientation fields. Sampling prototypical vector field patterns around defects shows that the robustness increases with the length of template path, but less so in the presence of noise on the vectors. We therefore find an optimal trade-off between resolution and robustness against noise for relatively small templates, except for the "single pixel" defect analysis, which cannot exclude zero robustness. The presented robustness measure paves the way for uncertainty quantification of defects in discretized vector fields.