Computational Mathematics and Applications

Current methods for globalizing Newton's Method for solving systems of nonlinear equations fall back on steps biased towards the steepest descent direction (e.g. Levenberg/Marquardt, Trust regions, Cauchy point dog-legs etc.), when there is difficulty in making progress. This can occasionally lead to very slow convergence when short steps are repeatedly taken.

This talk looks at alternative strategies based on searching curved arcs related to Davidenko trajectories. Near to manifolds on which the Jacobian matrix is singular, certain conjugate steps are also interleaved, based on identifying a Pareto optimal solution.

Preliminary limited numerical experiments indicate that this approach is very effective, with rapid and ultimately second order convergence in almost all cases. It is hoped to present more detailed numerical evidence when the talk is given. The new ideas can also be incorporated with more recent ideas such as multifilters or nonmonotonic line searches without difficulty, although it may be that there is no longer much to gain by doing this.

The famous Eckart-Young Theorem states that the (normwise) condition number of a matrix is equal to the reciprocal of its distance to the nearest singular matrix. In a recent paper we proved an extension of this to a number of structures common in matrix analysis, i.e. the structured condition number is equal to the reciprocal of the structured distance to the nearest singular matrix. In this talk we present a number of related results on structured eigenvalue perturbations and structured pseudospectra, for normwise and for componentwise perturbations.

First, I'll give a very brief update on our nonlinear Krylov accelerator for the usual Modified Newton's method. This simple accelerator, which I devised and Neil Carlson implemented as a simple two page Fortran add-on to our implicit stiff ODEs solver, has been robust, simple, cheap, and automatic on all our moving node computations since 1990. I publicize further experience with it here, by us and by others in diverse fields, because it is proving to be of great general usefulness, especially for solving nonlinear evolutionary PDEs or a smooth succession of steady states.

Second, I'll report on some recent work in computerized tomography from X-rays. With colored computer graphics I'll explain how the standard "filtered backprojection" method works for the classical 2D parallel beam problem. Then with that backprojection kernel function H(t) we'll use an integral "change of variables" approach for the 2D fan-beam geometry. Finally, we turn to the tomographic reconstruction of a 3D object f(x,y,z) from a wrapped around cylindical 2D array of detectors opposite a 2D array of sources, such as occurs in PET (positron-emission tomography) or in very-wide-cone-beam tomography with a finely spaced source spiral.