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
    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
    0 references
    0 references

    Identifiers