liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
A greedy algorithm for the optimal basis problem
Parallel Algorithms Team, CERFACS, Toulouse Cedex, France.ORCID iD: 0000-0003-1836-4200
1997 (English)In: BIT Numerical Mathematics, ISSN 0006-3835, E-ISSN 1572-9125, Vol. 37, no 3, 591-599 p.Article in journal (Refereed) Published
Abstract [en]

The following problem is considered. Given m+1 points {x i }0 m in R n which generate an m-dimensional linear manifold, construct for this manifold a maximally linearly independent basis that consists of vectors of the form x i x j . This problem is present in, e.g., stable variants of the secant and interpolation methods, where it is required to approximate the Jacobian matrix f′ of a nonlinear mappingf by using values off computed at m+1 points. In this case, it is also desirable to have a combination of finite differences with maximal linear independence. As a natural measure of linear independence, we consider the hadamard condition number which is minimized to find an optimal combination of m pairs {x i ,x j }. We show that the problem is not NP-hard, but can be reduced to the minimum spanning tree problem, which is solved by the greedy algorithm in O(m 2) time. The complexity of this reduction is equivalent to one m×n matrix-matrix multiplication, and according to the Coppersmith-Winograd estimate, is below O(n 2.376) for m=n. Applications of the algorithm to interpolation methods are discussed.

Place, publisher, year, edition, pages
Springer, 1997. Vol. 37, no 3, 591-599 p.
Keyword [en]
Optimal basis problem; the Hadamard condition number; minimum spanning tree problem; greedy algorithm; secant approximation of derivatives; interpolation methods
National Category
Computational Mathematics
URN: urn:nbn:se:liu:diva-78866DOI: 10.1007/BF02510241OAI: diva2:536299
Available from: 2012-06-21 Created: 2012-06-21 Last updated: 2015-06-02

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Burdakov, Oleg
In the same journal
BIT Numerical Mathematics
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 40 hits
ReferencesLink to record
Permanent link

Direct link