Superlinear convergence of conjugate gradients
Abstract
The convergence of Krylov subspace methods like conjugate gradients
depends on the eigenvalues of the underlying matrix. In many cases
the exact location of the eigenvalues is unknown, but one has some
information about the distribution of eigenvalues in an asymptotic
sense. This could be the case for linear systems arising from a
discretization of a PDE. The asymptotic behavior then takes place
when the meshsize tends to zero.
\\
\\
We discuss two possible approaches to study the convergence of
conjugate gradients based on such information.
The first approach is based on a straightforward idea to estimate
the condition number. This method is illustrated by means of a
comparison of preconditioning techniques.
The second approach takes into account the full asymptotic
spectrum. It gives a bound on the asymptotic convergence factor
which explains the superlinear convergence observed in many situations.
This method is mathematically more involved since it deals with
potential theory. I will explain the basic ideas.
Sobolev index estimation for hp-adaptive finite element methods
Abstract
We develop an algorithm for estimating the local Sobolev regularity index
of a given function by monitoring the decay rate of its Legendre expansion
coefficients. On the basis of these local regularities, we design and
implement an hp--adaptive finite element method based on employing
discontinuous piecewise polynomials, for the approximation of nonlinear
systems of hyperbolic conservation laws. The performance of the proposed
adaptive strategy is demonstrated numerically.
Recent results on accuracy and stability of numerical algorithms
Abstract
The study of the finite precision behaviour of numerical algorithms dates back at least as far as Turing and Wilkinson in the 1940s. At the start of the 21st century, this area of research is still very active.
We focus on some topics of current interest, describing recent developments and trends and pointing out future research directions. The talk will be accessible to those who are not specialists in numerical analysis.
Specific topics intended to be addressed include
- Floating point arithmetic: correctly rounded elementary functions, and the fused multiply-add operation.
- The use of extra precision for key parts of a computation: iterative refinement in fixed and mixed precision.
- Gaussian elimination with rook pivoting and new error bounds for Gaussian elimination.
- Automatic error analysis.
- Application and analysis of hyperbolic transformations.
Real symmetric matrices with multiple eigenvalues
Abstract
We describe "avoidance of crossing" and its explanation by von
Neumann and Wigner. We show Lax's criterion for degeneracy and then
discover matrices whose determinants give the discriminant of the
given matrix. This yields a simple proof of the bound given by
Ilyushechkin on the number of terms in the expansion of the discriminant
as a sum of squares. We discuss the 3 x 3 case in detail.
Some complexity considerations in sparse LU factorization
Abstract
The talk will discuss unsymmetric sparse LU factorization based on
the Markowitz pivot selection criterium. The key question for the
author is the following: Is it possible to implement a sparse
factorization where the overhead is limited to a constant times
the actual numerical work? In other words, can the work be bounded
by o(sum(k, M(k)), where M(k) is the Markowitz count in pivot k.
The answer is probably NO, but how close can we get? We will give
several bad examples for traditional methods and suggest alternative
methods / data structure both for pivot selection and for the sparse
update operations.
Filtering & signal processing
Abstract
We discuss two filters that are frequently used to smooth data.
One is the (nonlinear) median filter, that chooses the median
of the sample values in the sliding window. This deals effectively
with "outliers" that are beyond the correct sample range, and will
never be chosen as the median. A straightforward implementation of
the filter is expensive for large windows, particularly in two dimensions
(for images).
\\
\\
The second filter is linear, and known as "Savitzky-Golay". It is
frequently used in spectroscopy, to locate positions and peaks and
widths of spectral lines. This filter is based on a least-squares fit
of the samples in the sliding window to a polynomial of relatively
low degree. The filter coefficients are unlike the equiripple filter
that is optimal in the maximum norm, and the "maxflat" filters that
are central in wavelet constructions. Should they be better known....?
\\
\\
We will discuss the analysis and the implementation of both filters.
Asymptotic rates of convergence - for quadrature, ODEs and PDEs
Abstract
The asymptotic rate of convergence of the trapezium rule is
defined, for smooth functions, by the Euler-Maclaurin expansion.
The extension to other methods, such as Gauss rules, is straightforward;
this talk begins with some special cases, such as Periodic functions, and
functions with various singularities.
\\
\\
Convergence rates for ODEs (Initial and Boundary value problems)
and for PDEs are available, but not so well known. Extension to singular
problems seems to require methods specific to each situation. Some of
the results are unexpected - to me, anyway.
A toolbox for optimal design
Abstract
In the past few years we have developed some expertise in solving optimization
problems that involve large scale simulations in various areas of Computational
Geophysics and Engineering. We will discuss some of those applications here,
namely: inversion of seismic data, characterization of piezoelectrical crystals
material properties, optimal design of piezoelectrical transducers and
opto-electronic devices, and the optimal design of steel structures.
\\
\\
A common theme among these different applications is that the goal functional
is very expensive to evaluate, often, no derivatives are readily available, and
some times the dimensionality can be large.
\\
\\
Thus parallelism is a need, and when no derivatives are present, search type
methods have to be used for the optimization part. Additional difficulties can
be ill-conditioning and non-convexity, that leads to issues of global
optimization. Another area that has not been extensively explored in numerical
optimization and that is important in real applications is that of
multiobjective optimization.
\\
\\
As a result of these varied experiences we are currently designing a toolbox
to facilitate the rapid deployment of these techniques to other areas of
application with a minimum of retooling.
Analysis of some structured preconditioners for saddle point problems
A-Posteriori error estimates for higher order Godunov finite volume methods on unstructured meshes
Abstract
A-Posteriori Error estimates for high order Godunov finite
volume methods are presented which exploit the two solution
representations inherent in the method, viz. as piecewise
constants $u_0$ and cell-wise $q$-th order reconstructed
functions $R^0_q u_0$. The analysis provided here applies
directly to schemes such as MUSCL, TVD, UNO, ENO, WENO or any
other scheme that is a faithful extension of Godunov's method
to high order accuracy in a sense that will be made precise.
Using standard duality arguments, we construct exact error
representation formulas for derived functionals that are
tailored to the class of high order Godunov finite volume
methods with data reconstruction, $R^0_q u_0$. We then consider
computable error estimates that exploit the structure of higher
order Godunov finite volume methods. The analysis technique used
in this work exploits a certain relationship between higher
order Godunov methods and the discontinuous Galerkin method.
Issues such as the treatment of nonlinearity and the optional
post-processing of numerical dual data are also discussed.
Numerical results for linear and nonlinear scalar conservation
laws are presented to verify the analysis. Complete details can
be found in a paper appearing in the proceedings of FVCA3,
Porquerolles, France, June 24-28, 2002.
SMP parallelism: Current achievements, future challenges
Abstract
SMP (Symmetric Multi-Processors) hardware technologies are very popular
with vendors and end-users alike for a number of reasons. However, true
shared memory parallelism has experienced somewhat slower to take up
amongst the scientific-programming community. NAG has been at the
forefront of SMP technology for a number of years, and the NAG SMP
Library has shown the potential of SMP systems.
\\
\\
At the very high end, SMP hardware technologies are used as building
blocks of modern supercomputers, which truly consist of clusters of SMP
systems, for which no dedicated model of parallelism yet exists.
\\
\\
The aim of this talk is to introduce SMP systems and their potential.
Results from our work at NAG will also be introduced to show how SMP
parallelism, based on a shared memory paradigm, can be used to very
good effect and can produce high performance, scalable software. The
talk also aims to discuss some aspects of the apparent slow take up of
shared memory parallelism and the potential competition from PC (i.e.
Intel)-based cluster technology. The talk then aims to explore the
potential of SMP technology within "hybrid parallelism", i.e. mixed
distributed and shared memory modes, illustrating the point with some
preliminary work carried out by the author and others. Finally, a
number of potential future challenges to numerical analysts will be
discussed.
\\
\\
The talk is aimed at all who are interested in SMP technologies for
numerical computing, irrespective of any previous experience in the
field. The talk aims to stimulate discussion, by presenting some ideas,
backing these with data, not to stifle it in an ocean of detail!
Computed tomography for X-rays: old 2-D results, relevance to new 3-D spiral CT problems
Oscillations in discrete solutions to the convection-diffusion equation
Abstract
It is well known that discrete solutions to the convection-diffusion
equation contain nonphysical oscillations when boundary layers are present
but not resolved by the discretisation. For the Galerkin finite element
method with linear elements on a uniform 1D grid, a precise statement as
to exactly when such oscillations occur can be made, namely, that for a
problem with mesh size h, constant advective velocity and different values
at the left and right boundaries, oscillations will occur if the mesh
P\'{e}clet number $P_e$ is greater than one. In 2D, however, the situation
is not so well understood. In this talk, we present an analysis of a 2D
model problem on a square domain with grid-aligned flow which enables us
to clarify precisely when oscillations occur, and what can be done to
prevent them. We prove the somewhat surprising result that there are
oscillations in the 2D problem even when $P_e$ is less than 1. Also, we show that there
are distinct effects arising from differences in the top and bottom
boundary conditions (equivalent to those seen in 1D), and the non-zero
boundaries parallel to the flow direction.
Algebraic modeling systems and mathematical programming
Abstract
Algebra based modeling systems are becoming essential elements in the
application of large and complex mathematical programs. These systems
enable the abstraction, expression and translation of practical
problems into reliable and effective operational systems. They provide
the bridged between algorithms and real world problems by automating
the problem analysis and translation into specific data structures and
provide computational services required by different solvers. The
modeling system GAMS will be used to illustrate the design goals and
main features of such systems. Applications in use and under
development will be used to provide the context for discussing the
changes in user focus and future requirements. This presents new sets
of opportunities and challenges to the supplier and implementer of
mathematical programming solvers and modeling systems.
Adaptive finite elements for optimal control
Abstract
A systematic approach to error control and mesh adaptation for
optimal control of systems governed by PDEs is presented.
Starting from a coarse mesh, the finite element spaces are successively
enriched in order to construct suitable discrete models.
This process is guided by an a posteriori error estimator which employs
sensitivity factors from the adjoint equation.
We consider different examples with the stationary Navier-Stokes
equations as state equation.
On the condition number of bases in Banach spaces
Iterative methods for PDE eigenvalue problems
Abstract
Finite Element approximation of surfactant spreading on a thin film
A new preconditioning technique for the solution of the biharmonic problem
Abstract
In this presentation we examine the convergence characteristics of a
Krylov subspace solver preconditioned by a new indefinite
constraint-type preconditioner, when applied to discrete systems
arising from low-order mixed finite element approximation of the
classical biharmonic problem. The preconditioning operator leads to
preconditioned systems having an eigenvalue distribution consisting of
a tightly clustered set together with a small number of outliers. We
compare the convergence characteristics of a new approach with the
convergence characteristics of a standard block-diagonal Schur
complement preconditioner that has proved to be extremely effective in
the context of mixed approximation methods.
\\
\\
In the second part of the presentation we are concerned with the
efficient parallel implementation of proposed algorithm on modern
shared memory architectures. We consider use of the efficient parallel
"black-box'' solvers for the Dirichlet Laplacian problems based on
sparse Cholesky factorisation and multigrid, and for this purpose we
use publicly available codes from the HSL library and MGNet collection.
We compare the performance of our algorithm with sparse direct solvers
from the HSL library and discuss some implementation related issues.
Distribution tails of condition numbers for the polyhedral conic feasibility problem
Abstract
(Joint work with Felipe Cucker and Dennis Cheung, City University of Hong Kong.)
\\
\\
Condition numbers are important complexity-theoretic tools to capture
a "distillation" of the input aspects of a computational problem that
determine the running time of algorithms for its solution and the
sensitivity of the computed output. The motivation for our work is the
desire to understand the average case behaviour of linear programming
algorithms for a large class of randomly generated input data in the
computational model of a machine that computes with real numbers. In
this model it is not known whether linear programming is polynomial
time solvable, or so-called "strongly polynomial". Closely related to
linear programming is the problem of either proving non-existence of
or finding an explicit example of a point in a polyhedral cone defined
in terms of certain input data. A natural condition number for this
computational problem was developed by Cheung and Cucker, and we analyse
its distributions under a rather general family of input distributions.
We distinguish random sampling of primal and dual constraints
respectively, two cases that necessitate completely different techniques
of analysis. We derive the exact exponents of the decay rates of the
distribution tails and prove various limit theorems of complexity
theoretic importance. An interesting result is that the existence of
the k-th moment of Cheung-Cucker's condition number depends only very
mildly on the distribution of the input data. Our results also form
the basis for a second paper in which we analyse the distributions of
Renegar's condition number for the randomly generated linear programming
problem.