Optimization and Systems Theory Seminar
Friday, April 30, 1999, 11.00-12.00, Room 3721, Lindstedtsvägen 25


Associate Professor Oleg Burdakov
Division of Optimization
Department of Mathematics
Linköping University
E-mail: burdakov@mai.liu.se

A greedy algorithm for the optimal basis problem and its application to interpolation methods

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 and interpolation methods, where it is required to approximate the Jacobian matrix f' of a nonlinear mapping f by using values of f 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 {xi,xj}. 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(m2) time. The complexity of this reduction is equivalent to one m x n matrix-matrix multiplication, and according to the Coppersmith-Winograd estimate, is below O(n2.376) for m=n. Applications of the algorithm to interpolation methods for solving nonlinear equations are discussed.
Calendar of seminars
Last update: April 7, 1999 by Anders Forsgren, anders.forsgren@math.kth.se.