Speaker: Stefano Massei
Affiliation: EPF Lausanne, Switzerland
Time: Wednesday, 04/12/2019, 11:00
Place: Sala Seminari Est, Dipartimento di Informatica.
Title: Rational Krylov for Stieltjes matrix functions: convergence and
pole selection
Evaluating the action of a matrix function on a vector, that is x =
f(M)v, is an ubiquitous task in applications. When the matrix M is
large, subspace projection method, such as the rational Krylov method,
are usually employed. In this work, we provide a quasi-optimal pole
choice for rational Krylov methods applied to this task when f(z) is
either Cauchy-Stieltjes or Laplace-Stieltjes (or, which is equivalent,
completely monotonic) for a positive definite matrix M.
Then, we consider the case when the argument M has the Kronecker
structure M = I⊗A - B^T⊗I, and is applied to a vector obtained
vectorizing a low-rank matrix. This finds application, for instance, in
solving fractional diffusion equation on rectangular domains. We
introduce an error analysis for the numerical approximation of x. Pole
choices and explicit convergence bounds are given also in this case.
https://www.dm.unipi.it/webnew/it/seminari/rational-krylov-stieltjes-matrix…
Speaker: Gerald Williams
Affiliation: University of Essex, UK
Time: Wednesday, 27/11/2019, 11:00
Place: Aula Magna, Dipartimento di Matematica
Title: The role of circulant matrices in the study of cyclically
presented groups
A circulant matrix is a square matrix in which each row is obtained from
its predecessor by a cyclic shift by one column. A cyclically presented
group is one that is defined by a group presentation (ie a description
of a group in terms of generators and defining relations) that admits a
similar cyclic symmetry. Prominent examples are the Fibonacci groups,
where the presentations' defining relations mimic the Fibonacci
recurrence relation.
Questions that arise when studying cyclically presented groups ask when
such a group is finite or perfect, when it is 3-manifold group or knot
group; if so, what more can we say about the group. Knowledge of the
determinant, rank, and the Smith normal form of a related circulant
matrix can help to answer these questions.
In this talk I will discuss how well-known properties of circulant
matrices have been used to gain insight into the structure of cyclically
presented groups, and discuss recent and ongoing work with Vanni
Noferini that is advancing the theory to provide new tools for studying
such groups.
https://www.dm.unipi.it/webnew/it/seminari/role-circulant-matrices-study-cy…
Speaker: Enrico Facca
Affiliation: Scuola Normale Superiore, Pisa
Time: Wednesday, 20/11/2019, 11:00
Place: Aula Tonelli, SNS
Title: A bio-inspired optimization tool, the Dynamic
Monge-Kantorovich model. Numerical solutions and applications
In this talk I will present the Dynamical
Monge-Kantorovich model, a PDE system coupling an elliptic
equation with a diffusion coefficient that change in time
according to a non-linear dynamics.
The steady state of this system has been related to the
different Optimal Transport problems, offering an efficient
numerical scheme for their solution. We will explore some
examples of application, like identification of the
Cut-Locus of a point on manifold and the study of complex
natural network.
The simplicity of the model allows simple but effective
transformations of its core equations, that have been shown
to be connected with different optimization problems,
such as the Basis Pursuit Problem and the Shape
Optimization Problem.
https://www.dm.unipi.it/webnew/it/seminari/bio-inspired-optimization-tool-d…
Segnalo la presenza di questo colloquio, che non fa parte della nostra serie di seminari ma ha un tema che potrebbe essere di interesse per gli iscritti alla lista.
È una "lectio magistralis" che fa parte delle celebrazioni per i 50 anni del corso di laurea in informatica. Si terrà nell'aula magna del polo Pontecorvo (edificio E) lunedì 18 novembre alle 15:30.
Cordialmente,
-federico
-------- Forwarded Message --------
Subject: [Dipartimento.di] Lectio Luca Trevisan
Date: Fri, 15 Nov 2019 09:55:55 +0100
From: Gian Luigi Ferrari <gian-luigi.ferrari(a)unipi.it>
To: CDD <cdd(a)di.unipi.it>, dipartimento(a)di.unipi.it
Lo avevo comunicato in consiglio ma mi sono scordato di mandarlo via mail.
Rimedio
Title: A Theory of Spectral Clustering
Speaker: Luca Trevisan
Abstract: Spectral clustering algorithms find clusters in a given network by exploiting properties of the eigenvectors of matrices associated with the network. As a first step, one computes a spectral embedding, that is a mapping of nodes to points in a low-dimensional real space; then one uses geometric clustering algorithms such as k-means to cluster the points corresponding to the nodes.
Such algorithms work so well that, in certain applications unrelated to network analysis, such as image segmentation, it is useful to associate a network to the data, and then apply spectral clustering to the network. In addition to its application to clustering, spectral embeddings are a valuable tool for dimension-reduction and data visualization.
The performance of spectral clustering algorithms has been justified rigorously when applied to networks coming from certain probabilistic generative models.
A more recent development, which is the focus of this lecture, is a worst-case analysis of spectral clustering, showing that, for every graph that exhibits a certain cluster structure, such structure can be found by geometric algorithms applied to a spectral embedding.
Such results generalize the graph Cheeger’s inequality (a classical result in spectral graph theory), and they have additional applications in computational complexity theory and in pure mathematics.
———
Bio: Luca Trevisan is a professor of Computer Science at Bocconi University. Luca studied at the Sapienza University of Rome, he was a post-doc at MIT and at DIMACS, and he was on the faculty of Columbia University, U.C. Berkeley, and Stanford, before returning to Berkeley in 2014 and, at long last, moving back to Italy in 2019.
Luca's research is in theoretical computer science, and it is focused on computational complexity and graph algorithms.
Luca received the STOC'97 Danny Lewin (best student paper) award, the 2000 Oberwolfach Prize, and the 2000 Sloan Fellowship. He was an invited speaker at the 2006 International Congress of Mathematicians. He is a recipient of a 2019 ERC Advanced Grant.
______________________________________________
Dipartimento.di mailing list
Dipartimento.di(a)listgateway.unipi.it
http://listgateway.unipi.it/mailman/listinfo/dipartimento.di
Speaker: Massimiliano Fasi
Affiliation: Department of Mathematics, The University of Manchester
Time: Wednesday, 13/11/2019, 11:00
Place: Aula Seminari, Dipartimento di Matematica
Title: Handling the conditioning of extreme-scale matrices
In order to assess experimentally the stability of algorithms for
the solution of systems of linear equations, it is typically
desirable to have a certain degree of control over the condition
number of the test matrices being used. If the tests are being
performed at scale (e.g., in an HPL benchmark run for a TOP500
submission), it is necessary to ensure that generating the test
data will take up only a negligible portion of the overall
execution time required to solve the linear system. We develop two
new techniques that satisfy these requirements and can be used to
efficiently construct extremely large matrices with preassigned
2-norm condition number. Focusing on distributed memory
environments, we discuss how these can be implemented in a
communication-avoiding fashion.
https://www.dm.unipi.it/webnew/it/seminari/handling-conditioning-extreme-sc…
