A greedy algorithm for the optimal basis problem (Q1371665)

The authors consider the problem of finding an optimal basis of the vectors of the form \(x_i-x_j\) of an \(m\)-dimensional linear manifold generated by \(m+1\) vectors \(\{x_\ell\mid \ell=0,\dots, m\}\) in \(\mathbb{R}^n\). Such a problem occurs in multipoint interpolation methods for solving systems of nonlinear equations. The formulation of the problem is based on a graph representation using the Hadamard condition number as a measure of linear independence for non-zero vectors. An algorithm for finding the optimal basis is developed after reducing the original problem to the minimum spanning tree problem. Applications of the algorithm to interpolation methods are discussed.