报告题目：Optimal basis algorithm and its application to interpolation and matrix scaling

报告人：Prof. Oleg Burdakov

主持人：孙聪

报告时间：2017年11月9日10：00-11：00

报告地点：教三308

报告摘要：

We present the optimal basis (OB) problem and the OB algorithm that we proposed in BIT (1997) 37, 591-599. The OB problem is formulated as follows. Given m+1 points $\{x_i\}_0^m$ 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 $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\}$ that defines the optimal basis. This 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[1]n matrix{matrix multiplication, and according to the Coppersmith-Winograd estimate, is below $O(n^{2.376})$ for m = n. We discuss possible applications of the OB algorithm for constructing simple non-diagonal prescaling procedures for iterative linear algebra solvers.

报告人简介：

Oleg Burdakov教授硕士和博士均毕业于俄罗斯莫斯科物理与科技研究所，目前是瑞典林雪平大学的教授。他的研究方向包括优化问题和非线性方程组的数值解法，如牛顿法、插值方法等；以及图论中的扩展最短路问题、Steiner树问题等。他曾获得美国离散数学和理论计算科学中心组织的Steiner树问题国际挑战赛的冠军，还曾获得前苏联国家成就经济展铜奖。目前Burdakov教授担任期刊《Optimization Methods and Software》的主编，也是包括SIAM Optimation在内的多个国际知名期刊的审稿人。