Computational Mathematics and Applications
|
Thu, 13/10/2011 14:00 |
Dr Peter Richtárik (University of Edinburgh) |
Computational Mathematics and Applications  |
Gibson Grd floor SR |
We develop a randomized block-coordinate descent method for minimizing the sum of a smooth and a simple nonsmooth block-separable convex function and prove that it obtains an  -accurate solution with probability at least  in at most ![$ O[(2n/\epsilon)\log(1/\rho)] $](/files/tex/56f45a40668a57353d0b252644534b9feb5d445d.png) iterations, where  is the dimension of the problem. For strongly convex functions the method converges linearly. This extends recent results of Nesterov [Efficiency of coordinate descent methods on huge-scale optimization problems, CORE Discussion Paper #2010/2], which cover the smooth case, to composite minimization, while at the same time improving the complexity by the factor of 4 and removing from the logarithm. More importantly, in contrast with the aforementioned work in which the authors achieve the results by applying their method to a regularized version of the objective function with an unknown scaling factor, we show that this is not necessary, thus achieving true iteration complexity bounds. In the smooth case we also allow for arbitrary probability vectors and non-Euclidean norms. Time permitting, we will also mention new iteration complexity results for a parallel version of the method.
In the second part of the talk we demonstrate numerically that the algorithm is able to solve huge-scale  -regularized support vector machine and least squares problems with billion variables. Finally, we present preliminary computational results with a GPU-accelerated parallel version of the method, on truss topology design instances, achieving speedups of up to two orders of magnitude when compared to a single-core implementation in C.
References: P. Richtarik and M. Takac, Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function, 2011; http://arxiv.org/abs/1107.2848 P. Richtarik and M. Takac, Efficient serial and parallel coordinate descent methods for huge-scale truss topology design, 2011; http://www.optimization-online.org/DB_HTML/2011/08/3118.html P. Richtarik and M. Takac, Efficiency of randomized coordinate descent methods on minimization problems with a composite objective function, Proceedings of SPARS11 |
|||
|
Thu, 20/10/2011 14:00 |
Prof Hans Munthe-Kaas (University of Bergen) |
Computational Mathematics and Applications |
Gibson Grd floor SR |
|
Thu, 27/10/2011 14:00 |
Prof Joerg Liesen (Technical University of Berlin) |
Computational Mathematics and Applications |
Gibson Grd floor SR |
| We will study the question of whether the adjoint of a given matrix can be written as a rational function in the matrix. After showing necessary and sufficient conditions, rational interpolation theory will help to characterize the most important existing cases. Several topics related to our question will be explored. They range from short recurrence Krylov subspace methods to the roots of harmonic polynomials and harmonic rational functions. The latter have recently found interesting applications in astrophysics, which will briefly be discussed as well. | |||
|
Thu, 03/11/2011 14:00 |
Dr Bora Ucar (ENS Lyon) |
Computational Mathematics and Applications |
Rutherford Appleton Laboratory, nr Didcot |
We will discuss the use of hypergraph-based methods for orderings of sparse matrices in Cholesky, LU and QR factorizations. For the Cholesky factorization case, we will investigate a recent result on pattern-wise decomposition of sparse matrices, generalize the result and develop algorithmic tools to obtain effective ordering methods. We will also see that the generalized results help us formulate the ordering problem in LU much like we do for the Cholesky case, without ever symmetrizing the given matrix  as  or  . For the QR factorization case, the use of hypergraph models is fairly standard. We will nonetheless highlight the fact that the method again does not form the possibly much denser matrix . We will see comparisons of the hypergraph-based methods with the most common alternatives in all three cases.
This is joint work with Iain S. Duff. |
|||
|
Thu, 10/11/2011 14:00 |
Dr Shahrokh Shahpar (Rolls Royce plc.) |
Computational Mathematics and Applications |
Gibson Grd floor SR |
|
Computational Fluid Dynamics (CFD) has become an
indispensable tool in designing turbomachinery components in all sectors of
Rolls-Royce business units namely, Aerospace, Industrial, Marine and Nuclear.
Increasingly sophisticated search and optimisation techniques are used based on
both traditional optimisation methods as well as, design of computer experiment
techniques, advanced surrogate methods, and evolutionary optimisation
techniques. Geometry and data representation as well as access, queuing and
loading control of large high performance computing clusters are areas of
research to establish the most efficient techniques for improving the
performance of an already highly efficient modern jet engine.
This presentation focuses on a high fidelity design optimisation framework called SOPHY that is used in Rolls-Royce to provide parametric geometry, automatic meshing, advanced design-space search algorithms, accurate and robust CFD methodology and post-processing. The significance of including the so-called real geometry features and interaction of turbomachinery components in the optimisation cycle are discussed. Examples are drawn from real world applications of the SOPHY design systems in an engine project. |
|||
|
Thu, 17/11/2011 14:00 |
Prof Nancy Nichols (University of Reading) |
Computational Mathematics and Applications |
Rutherford Appleton Laboratory, nr Didcot |
| Variational data assimilation techniques for optimal state estimation in very large environmental systems currently use approximate Gauss-Newton (GN) methods. The GN method solves a sequence of linear least squares problems subject to linearized system constraints. For very large systems, low resolution linear approximations to the model dynamics are used to improve the efficiency of the algorithm. We propose a new approach for deriving low order system approximations based on model reduction techniques from control theory which can be applied to unstable stochastic systems. We show how this technique can be combined with the GN method to retain the response of the dynamical system more accurately and improve the performance of the approximate GN method. | |||
|
Thu, 24/11/2011 14:00 |
Prof Ping Lin (University of Dundee) |
Computational Mathematics and Applications |
Gibson Grd floor SR |
| The liquid crystal (LC) flow model is a coupling between orientation (director field) of LC molecules and a flow field. The model may probably be one of simplest complex fluids and is very similar to a Allen-Cahn phase field model for multiphase flows if the orientation variable is replaced by a phase function. There are a few large or small parameters involved in the model (e.g. the small penalty parameter for the unit length LC molecule or the small phase-change parameter, possibly large Reynolds number of the flow field, etc.). We propose a C^0 finite element formulation in space and a modified midpoint scheme in time which accurately preserves the inherent energy law of the model. We use C^0 elements because they are simpler than existing C^1 element and mixed element methods. We emphasise the energy law preservation because from the PDE analysis point of view the energy law is very important to correctly catch the evolution of singularities in the LC molecule orientation. In addition we will see numerical examples that the energy law preserving scheme performs better under some choices of parameters. We shall apply the same idea to a Cahn-Hilliard phase field model where the biharmonic operator is decomposed into two Laplacian operators. But we find that under our scheme non-physical oscillation near the interface occurs. We figure out the reason from the viewpoint of differential algebraic equations and then remove the non-physical oscillation by doing only one step of a modified backward Euler scheme at the initial time. A number of numerical examples demonstrate the good performance of the method. At the end of the talk we will show how to apply the method to compute a superconductivity model, especially at the regime of Hc2 or beyond. The talk is based on a few joint papers with Chun Liu, Qi Wang, Xingbin Pan and Roland Glowinski, etc. | |||
|
Thu, 01/12/2011 14:00 |
Prof Juan Restrepo (University of Arizona) |
Computational Mathematics and Applications |
Gibson Grd floor SR |
| The fundamental task in climate variability research is to eke out structure from climate signals. Ideally we want a causal connection between a physical process and the structure of the signal. Sometimes we have to settle for a correlation between these. The challenge is that the data is often poorly constrained and/or sparse. Even though many data gathering campaigns are taking place or are being planned, the very high dimensional state space of the system makes the prospects of climate variability analysis from data alone impractical. Progress in the analysis is possible by the use of models and data. Data assimilation is one such strategy. In this talk we will describe the methodology, illustrate some of its challenges, and highlight some of the ways our group has proposed to improving the methodology. | |||
