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.