Title:The omega-Condition Number: Applications to Preconditioning and Low Rank Generalized Jacobian Updating
| Speaker: | Henry Wolkowicz |
| Affiliation: | University of À¶Ý®ÊÓƵ |
| Location: | MC 5501 |
´¡²ú²õ³Ù°ù²¹³¦³Ù:ÌýPreconditioning is essential in iterative methods for solving linear systems. It is also the implicit objective in updating approximations of Jacobians in optimization methods, e.g.,~in quasi-Newton methods. We study a nonclassic matrix condition number, the omega-condition number}, omega for short. omega is the ratio of: the arithmetic and geometric means of the singular values, rather than the largest and smallest for the classical kappa-condition number. The simple functions in omega allow one to exploit first order optimality conditions. We use this fact to derive explicit formulae for (i) omega-optimal low rank updating of generalized Jacobians arising in the context of nonsmooth Newton methods; and (ii) omega-optimal preconditioners of special structure for  iterative methods for linear systems. In the latter context, we analyze the benefits of omega for (a) improving the clustering of eigenvalues; (b) reducing the number of iterations; and (c) estimating the actual condition of a linear system. Moreover we show strong theoretical connections between the omega-optimal preconditioners and incomplete Cholesky factorizations, and highlight the misleading effects arising from the inverse invariance of kappa. Our results confirm the efficacy of using the omega-condition number compared to the kappa-condition number.
(Joint work with: Woosuk L. Jung, David Torregrosa-Belen.)