A greedy algorithm for the optimal basis problem (Q1371665)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A greedy algorithm for the optimal basis problem |
scientific article |
Statements
A greedy algorithm for the optimal basis problem (English)
0 references
13 November 1997
0 references
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.
0 references
greedy algorithm
0 references
optimal basis problem
0 references
multipoint interpolation methods
0 references
systems of nonlinear equations
0 references
Hadamard condition number
0 references
minimum spanning tree problem
0 references