Past Computational Mathematics and Applications Seminar

13 March 2014
14:00
Professor Christian Kreuzer
Abstract
Adaptive finite element methods (AFEMs) with Dörflers marking strategy are known to converge with optimal asymptotical rates. Practical experiences show that AFEMs with a maximum marking strategy produces optimal results thereby being less sensitive to choices of the marking parameter. \\ \\ In this talk, we prove that an AFEM with a modified maximum strategy is even instance optimal for the total error, i.e., for the sum of the error and the oscillation. This is a non-asymptotical optimality result. Our approach uses new techniques based on the minimisation of the Dirichlet energy and a newly developed tree structure of the nodes of admissible triangulations.
  • Computational Mathematics and Applications Seminar
6 March 2014
14:00
Professor Andrew Stuart
Abstract
Many problems in the physical sciences require the determination of an unknown function from a finite set of indirect measurements. Examples include oceanography, oil recovery, water resource management and weather forecasting. The Bayesian approach to these problems is natural for many reasons, including the under-determined and ill-posed nature of the inversion, the noise in the data and the uncertainty in the differential equation models used to describe complex mutiscale physics. The object of interest in the Bayesian approach is the posterior probability distribution on the unknown field [1]. \\ \\ However the Bayesian approach presents a computationally formidable task as it results in the need to probe a probability measure on separable Banach space. Monte Carlo Markov Chain methods (MCMC) may be used to achieve this [2], but can be prohibitively expensive. In this talk I will discuss approximation of probability measures by a Gaussian measure, looking for the closest approximation with respect to the Kullback-Leibler divergence. This methodology is widely used in machine-learning [3]. In the context of target measures on separable Banach space which themselves have density with respect to a Gaussian, I will show how to make sense of the resulting problem in the calculus of variations [4]. Furthermore I will show how the approximate Gaussians can be used to speed-up MCMC sampling of the posterior distribution [5]. \\ \\ [1] A.M. Stuart. "Inverse problems: a Bayesian perspective." Acta Numerica 19(2010) and http://arxiv.org/abs/1302.6989 \\ [2] S.L.Cotter, G.O.Roberts, A.M. Stuart and D. White, "MCMC methods for functions: modifying old algorithms to make them faster". Statistical Science 28(2013). http://arxiv.org/abs/1202.0709 \\ [3] C.M. Bishop, "Pattern recognition and machine learning". Springer, 2006. \\ [4] F.J. Pinski G. Simpson A.M. Stuart H. Weber, "Kullback-Leibler Approximations for measures on infinite dimensional spaces." http://arxiv.org/abs/1310.7845 \\ [5] F.J. Pinski G. Simpson A.M. Stuart H. Weber, "Algorithms for Kullback-Leibler approximation of probability measures in infinite dimensions." In preparation.
  • Computational Mathematics and Applications Seminar
Dr Dmitry Savostyanov
Abstract

When high-dimensional problems are concerned, not much algorithms can break the curse of dimensionality, and solve them efficiently and reliably. Among those, tensor product algorithms, which implement the idea of separation of variables for multi-index arrays (tensors), seem to be the most general and also very promising. They originated in quantum physics and chemistry and descent broadly from the density matrix renormalization group (DMRG) and matrix product states (MPS) formalisms. The same tensor formats were recently re-discovered in the numerical linear algebra (NLA) community as the tensor train (TT) format.

Algorithms developed in the quantum physics community are based on the optimisation in tensor formats, that is performed subsequently for all components of a tensor format (i.e. all sites or modes).
The DMRG/MPS schemes are very efficient but very difficult to analyse, and at the moment only local convergence results for the simplest algorithm are available. In the NLA community, a common approach is to use a classical iterative scheme (e.g. GMRES) and enforce the compression to a tensor format at every step. The formal analysis is quite straightforward, but tensor ranks of the vectors which span the Krylov subspace grow rapidly with iterations, and the methods are struggling in practice.

The first attempt to merge classical iterative algorithms and DMRG/MPS methods was made by White (2005), where the second Krylov vector is used to expand the search space on the optimisation step.
The idea proved to be useful, but the implementation was based on the fair amount of physical intuition, and the algorithm is not completely justified.

We have recently proposed the AMEn algorithm for linear systems, that also injects the gradient direction in the optimisation step, but in a way that allows to prove the global convergence of the resulted scheme. The scheme can be easily applied for the computation of the ground state --- the differences to the algorithm of S. White are emphasized in Dolgov and Savostyanov (2013).
The AMEn scheme is already acknowledged in the NLA community --- for example it was recently applied for the computation of extreme eigenstates by Kressner, Steinlechner and Uschmajew (2013), using the block-TT format proposed by in Dolgov, Khoromskij, Oseledets and Savostyanov (2014).

At the moment, AMEn algorithm was applied
 - to simulate the NMR spectra of large molecules (such as ubiquitin),
 - to solve the Fokker-Planck equation for the non-Newtonian polymeric flows,
 - to the chemical master equation describing the mesoscopic model of gene regulative networks,
 - to solve the Heisenberg model problem for a periodic spin chain.
We aim to extend this framework and the analysis to other problems of NLA: eigenproblems, time-dependent problems, high-dimensional interpolation, and matrix functions;  as well as to a wider list of high-dimensional problems.

This is a joint work with Sergey Dolgov the from Max-Planck Institute for Mathematics in the Sciences, Leipzig, Germany.

  • Computational Mathematics and Applications Seminar
13 February 2014
14:00
Dr Leonardo Figueroa
Abstract
We report on a numerical implementation of a quasi-static model of rock detachment based on Allaire, Jouve and Van Goethem's implementation of Francfort and Marigo's model of damage in brittle solids, As such, local minimizers of a cost functional involving both stored elastic energy and a damage penalization term are sought by using a procedure which alternates between approximately solving a linear elasticity system and advancing a transport equation for a level set function describing the loci of still-attached rock. We pay special attention to the mixed finite element method used in the approximation of the linear elasticity system.
  • Computational Mathematics and Applications Seminar
6 February 2014
14:00
Professor Grady Wright
Abstract
Radial basis function (RBF) methods are becoming increasingly popular for numerically solving partial differential equations (PDEs) because they are geometrically flexible, algorithmically accessible, and can be highly accurate. There have been many successful applications of these techniques to various types of PDEs defined on planar regions in two and higher dimensions, and to PDEs defined on the surface of a sphere. Originally, these methods were based on global approximations and their computational cost was quite high. Recent efforts have focused on reducing the computational cost by using ``local’’ techniques, such as RBF generated finite differences (RBF-FD). In this talk, we first describe our recent work on developing a new, high-order, global RBF method for numerically solving PDEs on relatively general surfaces, with a specific focus on reaction-diffusion equations. The method is quite flexible, only requiring a set of ``scattered’’ nodes on the surface and the corresponding normal vectors to the surface at these nodes. We next present a new scalable local method based on the RBF-FD approach with this same flexibility. This is the first application of the RBF-FD method to general surfaces. We conclude with applications of these methods to some biologically relevant problems. This talk represents joint work with Edward Fuselier (High Point University), Aaron Fogelson, Mike Kirby, and Varun Shankar (all at the University of Utah).
  • Computational Mathematics and Applications Seminar
23 January 2014
14:00
Professor Luis Nunes Vicente
Abstract
Direct-search methods are a class of popular derivative-free algorithms characterized by evaluating the objective function using a step size and a number of (polling) directions. When applied to the minimization of smooth functions, the polling directions are typically taken from positive spanning sets which in turn must have at least n+1 vectors in an n-dimensional variable space. In addition, to ensure the global convergence of these algorithms, the positive spanning sets used throughout the iterations must be uniformly non-degenerate in the sense of having a positive (cosine) measure bounded away from zero. \\ \\ However, recent numerical results indicated that randomly generating the polling directions without imposing the positive spanning property can improve the performance of these methods, especially when the number of directions is chosen considerably less than n+1. \\ \\ In this talk, we analyze direct-search algorithms when the polling directions are probabilistic descent, meaning that with a certain probability at least one of them is of descent type. Such a framework enjoys almost-sure global convergence. More interestingly, we will show a global decaying rate of $1/\sqrt{k}$ for the gradient size, with overwhelmingly high probability, matching the corresponding rate for the deterministic versions of the gradient method or of direct search. Our analysis helps to understand numerical behavior and the choice of the number of polling directions. \\ \\ This is joint work with Clément Royer, Serge Gratton, and Zaikun Zhang.
  • Computational Mathematics and Applications Seminar
5 December 2013
14:00
Dr Gabriel Barrenechea
Abstract

We propose a strategy which allows computing eigenvalue enclosures for the Maxwell operator by means of the finite element method. The origins of this strategy can be traced back to over 20 years ago. One of its main features lies in the fact that it can be implemented on any type of regular mesh (structured or otherwise) and any type of elements (nodal or otherwise). In the first part of the talk we formulate a general framework which is free from spectral pollution and allows estimation of eigenfunctions.

We then prove the convergence of the method, which implies precise convergence rates for nodal finite elements. Various numerical experiments on benchmark geometries, with and without symmetries, are reported.

  • Computational Mathematics and Applications Seminar

Pages