The task of solving large scale linear algebraic problems such as factorising matrices or solving linear systems is of central importance in many areas of scientific computing, as well as in data analysis and computational statistics. The talk will describe how randomisation can be used to design algorithms that in many environments have both better asymptotic complexities and better practical speed than standard deterministic methods.

The talk will in particular focus on randomised algorithms for solving large systems of linear equations. Both direct solution techniques based on fast factorisations of the coefficient matrix, and techniques based on randomised preconditioners, will be covered.

Note: There is a related talk in the Random Matrix Seminar on Tuesday Feb 25, at 15:30 in L4. That talk describes randomised methods for computing low rank approximations to matrices. The two talks are independent, but the Tuesday one introduces some of the analytical framework that supports the methods described here.

In this talk I will present a Perron-Frobenius type result for nonlinear eigenvector problems which allows us to compute the global maximum of a class of constrained nonconvex optimization problems involving multihomogeneous functions.

I will structure the talk into three main parts:

First, I will motivate the optimization of homogeneous functions from a graph partitioning point of view, showing an intriguing generalization of the famous Cheeger inequality.

Second, I will define the concept of multihomogeneous function and I will state our main Perron-Frobenious theorem. This theorem exploits the connection between optimization of multihomogeneous functions and nonlinear eigenvectors to provide an optimization scheme that has global convergence guarantees.

Third, I will discuss a few example applications in network science and machine learning that require the optimization of multihomogeneous functions and that can be solved using nonlinear Perron eigenvectors.

Systems of nonlinear polynomial equations arise in a variety of fields in mathematics, science, and engineering.  Many numerical techniques for solving and analyzing solution sets of polynomial equations over the complex numbers, collectively called numerical algebraic geometry, have been developed over the past several decades.  However, since real solutions are the only solutions of interest in many applications, there is a current emphasis on developing new methods for computing and analyzing real solution sets.  This talk will summarize some numerical real algebraic geometric approaches as well as recent successes of these methods for solving a variety of problems in science and engineering.

(Joint work with: Jüri Lember, Heinrich Matzinger, Raul Kangro)

Principal component analysis is an important pattern recognition and dimensionality reduction tool in many applications and are computed as eigenvectors

of a maximum likelihood covariance that approximates a population covariance. The eigenvectors are often used to extract structural information about the variables (or attributes) of the studied population. Since PCA is based on the eigen-decomposition of the proxy covariance rather than the ground-truth, it is important to understand the approximation error in each individual eigenvector as a function of the number of available samples. The combination of recent results of Koltchinskii & Lounici [8] and Yu, Wang & Samworth [11] yields such bounds. In the presented work we sharpen these bounds and show that eigenvectors can often be reconstructed to a required accuracy from a sample of strictly smaller size order.

We discuss the design of algorithms and codes for the solution of large sparse systems of linear equations on extreme scale computers that are characterized by having many nodes with multi-core CPUs or GPUs. We first use two approaches to get good single node performance. For symmetric systems we use task-based algorithms based on an assembly tree representation of the factorization. We then use runtime systems for scheduling the computation on both multicore CPU nodes and GPU nodes [6]. In this work, we are also concerned with the efficient parallel implementation of the solve phase using the computed sparse factors, and we show impressive results relative to other state-of-the-art codes [3]. Our second approach was to design a new parallel threshold Markowitz algorithm [4] based on Luby’s method [7] for obtaining a maximal independent set in an undirected graph. This is a significant extension since our graph model is a directed graph. We then extend the scope of both these approaches to exploit distributed memory parallelism. In the first case, we base our work on the block Cimmino algorithm [1] using the ABCD software package coded by Zenadi in Toulouse [5, 8]. The kernel for this algorithm is the direct factorization of a symmetric indefinite submatrix for which we use the above symmetric code. To extend the unsymmetric code to distributed memory, we use the Zoltan code from Sandia [2] to partition the matrix to singly bordered block diagonal form and then use the above unsymmetric code on the blocks on the diagonal. In both cases, we illustrate the added parallelism obtained from combining the distributed memory parallelism with the high single-node performance and show that our codes out-perform other state-of-the-art codes. This work is joint with a number of people. We developed the algorithms and codes in an EU Horizon 2020 Project, called NLAFET, that finished on 30 April 2019. Coworkers in this were: Sebastien Cayrols, Jonathan Hogg, Florent Lopez, and Stojce ´ ∗@email 1 Nakov. Collaborators in the block Cimmino part of the project were: Philippe Leleux, Daniel Ruiz, and Sukru Torun. Our codes available on the github repository https://github.com/NLAFET.

References [1] M. ARIOLI, I. S. DUFF, J. NOAILLES, AND D. RUIZ, A block projection method for sparse matrices, SIAM J. Scientific and Statistical Computing, 13 (1992), pp. 47–70. [2] E. BOMAN, K. DEVINE, L. A. FISK, R. HEAPHY, B. HENDRICKSON, C. VAUGHAN, U. CATALYUREK, D. BOZDAG, W. MITCHELL, AND J. TERESCO, Zoltan 3.0: Parallel Partitioning, Load-balancing, and Data Management Services; User’s Guide, Sandia National Laboratories, Albuquerque, NM, 2007. Tech. Report SAND2007-4748W http://www.cs.sandia. gov/Zoltan/ug_html/ug.html. [3] S. CAYROLS, I. S. DUFF, AND F. LOPEZ, Parallelization of the solve phase in a task-based Cholesky solver using a sequential task flow model, Int. J. of High Performance Computing Applications, To appear (2019). NLAFET Working Note 20. RAL-TR-2018-008. [4] T. A. DAVIS, I. S. DUFF, AND S. NAKOV, Design and implementation of a parallel Markowitz threshold algorithm, Technical Report RAL-TR-2019-003, Rutherford Appleton Laboratory, Oxfordshire, England, 2019. NLAFET Working Note 22. Submitted to SIMAX. [5] I. S. DUFF, R. GUIVARCH, D. RUIZ, AND M. ZENADI, The augmented block Cimmino distributed method, SIAM J. Scientific Computing, 37 (2015), pp. A1248–A1269. [6] I. S. DUFF, J. HOGG, AND F. LOPEZ, A new sparse symmetric indefinite solver using a posteriori threshold pivoting, SIAM J. Scientific Computing, To appear (2019). NLAFET Working Note 21. RAL-TR-2018-012. [7] M. LUBY, A simple parallel algorithm for the maximal independent set problem, SIAM J. Computing, 15 (1986), pp. 1036–1053. [8] M. ZENADI, The solution of large sparse linear systems on parallel computers using a hybrid implementation of the block Cimmino method., These de Doctorat, ´ Institut National Polytechnique de Toulouse, Toulouse, France, decembre 2013.

Molecules are dynamical systems that can adopt a variety of three dimensional conformations which, in general, differ in energy and physical properties. The identification of energetically favourable conformations is fundamental in molecular physics and computational chemistry, since it is closely related to important open problems such as the prediction of the folding of proteins and virtual screening for drug design.
In this talk I will present theoretical and data-driven approaches to the study of molecular conformational spaces and their associated energy landscapes. I will show that the topology of the internal molecular conformational space might change after taking its quotient by the group action of a discrete group of symmetries. I will also show that geometric and topological tools for data analysis such as procrustes analysis, local dimensionality reduction, persistent homology and discrete Morse theory provide with efficient methods to study the mathematical structures underlying the molecular conformational spaces and their energy landscapes.
 

The reach is an important geometric invariant of submanifolds of Euclidean space. It is a real-valued global invariant incorporating information about the second fundamental form of the embedding and the location of the first critical point of the distance from the submanifold. In the subject of geometric inference, the reach plays a crucial role. I will give a new method of estimating the reach of a submanifold, developed jointly with Clément Berenfeld, Marc Hoffmann and Krishnan Shankar.

The talk will introduce two general models of random simplicial complexes which extend the highly studied Erdös-Rényi model for random graphs. These models include the well known probabilistic models of random simplicial complexes from Costa-Farber, Kahle, and Linial-Meshulam as special cases. These models turn out to have a satisfying Alexander duality relation between them prompting the hope that information can be transferred for free between them. This turns out to not quite be the case with vanishing probability parameters, but when all parameters are uniformly bounded the duality relation works a treat. Time permitting I may talk about the Rado simplicial complex, the unique (with probability one) infinite random simplicial complex.
This talk is based on various bits of joint work with Michael Farber, Tahl Nowik, and Lewin Strauss.