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

Direct link
On using the minimum spanning tree algorithm for optimal secant approximation of derivatives
CERFACS, Parallel Algorithms Team, Toulouse, France.ORCID iD: 0000-0003-1836-4200
1996 (English)In: Zeitschrift für angewandte Mathematik und Mechanik, ISSN 0044-2267, E-ISSN 1521-4001, Vol. 76, no S3, 389-390 p.Article in journal (Refereed) Published
Abstract [en]

The following problem is considered. Given m + 1 points {xi}0m in Rn which generate an m-dimensional linear manifold, construct for this manifold a maximally linearly independent basis that consists of vectors of the form xi - xj. This problem is present in, e.g., stable variants of the secant method, where it is required to approximate the Jacobian matrix f' of a nonlinear mapping f 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 a functional which is maximized to find an optimal combination of m pairs {xi, xj}. We show that the problem is not of combinatorial complexity but can be reduced to the minimum spanning tree (MST) problem, which is solved by an MST-type algorithm in O(m2n) time.

Place, publisher, year, edition, pages
1996. Vol. 76, no S3, 389-390 p.
National Category
Computational Mathematics
URN: urn:nbn:se:liu:diva-78873DOI: 10.1002/zamm.19960761312OAI: diva2:536320
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
Zeitschrift für angewandte Mathematik und Mechanik
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: 47 hits
ReferencesLink to record
Permanent link

Direct link