### 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
{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 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
{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 x 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 for solving nonlinear equations are
discussed.

Calendar of seminars

*Last update: April 7, 1999 by
Anders Forsgren,
anders.forsgren@math.kth.se.
*