A greedy algorithm for the optimal basis problem

作     者：Burdakov, O 

作者机构：CERFACS PARALLEL ALGORITHMS TEAM F-31057 TOULOUSE FRANCE 

出 版 物：《BIT NUMERICAL MATHEMATICS》 (BIT数值数学)

年 卷 期：1997年第37卷第3期

页      面：591-599页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0835[工学-软件工程] 0701[理学-数学] 

基　　金：NSF Science and Technology Center, (STC-91-19999) Princeton University, Princeton Center for Discrete Mathematics and Theoretical Computer Science, DIMACS 

主　　题：optimal basis problem the Hadamard condition number minimum spanning tree problem greedy algorithm secant approximation of derivatives 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 fl 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 are discussed.