| 1. |
- Burdakov, Oleg, 1953-
(författare)
-
A greedy algorithm for the optimal basis problem
- 1997
-
Ingår i: BIT Numerical Mathematics. - : Springer. - 0006-3835 .- 1572-9125. ; 37:3, s. 591-599
-
Tidskriftsartikel (refereegranskat)abstract
- 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 mappingf by using values off 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×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.
|
|
| 2. |
- Burdakov, Oleg, 1953-
(författare)
-
On properties of Newton's method for smooth and nonsmooth equations
- 1995
-
Ingår i: Recent Trends in Optimization Theory and Applications. - : World Scientific. - 9789810223823 - 9789812798862 ; , s. 17-24
-
Bokkapitel (övrigt vetenskapligt/konstnärligt)abstract
- Variational inequalities, nonlinear programming, complementarity problems and other problems can be reduced to nonsmooth equations, for which some generalizations of Newton's method are known. The Newton path, as a natural generalization of the Newton direction, was suggested by D.Ralph for enlarging the convergence region (globalization) of Newton-Robinson's method in the nonsmooth case. We investigate some properties of both the Newton direction and the Newton path, which seem to be basic for various globalization strategies. In particular, a simple formula for the derivative of an arbitrary norm of residuals along the Newton direction,derived earlier by the author for the smooth equations, is generalizedhere for the derivative along the Newton path.
|
|
| 3. |
- Burdakov, Oleg, 1953-
(författare)
-
On using the minimum spanning tree algorithm for optimal secant approximation of derivatives
- 1996
-
Ingår i: Zeitschrift für angewandte Mathematik und Mechanik. - : Wiley. - 0044-2267 .- 1521-4001. ; 76:S3, s. 389-390
-
Tidskriftsartikel (refereegranskat)abstract
- 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 method, where it is required to approximate the Jacobian matrix f' of a nonlinear mapping f by using values off 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 a functional which is maximized to find an optimal combination of m pairs {xi, xj}. We show that the problem is not of combinatorial complexity but can be reduced to the minimum spanning tree (MST) problem, which is solved by an MST-type algorithm in O(m2n) time.
|
|
