NumPI October 2015

numpi@lists.dm.unipi.it

2 participants
2 discussions

Optimization & Numerical Analysis seminars: Brugiapaglia
by Federico Poloni 23 Oct '15

23 Oct '15

Speaker: Simone Brugiapaglia Affiliation: Politecnico di Milano --- Laboratory for Modeling and Scientific Computing MOX Time: Tuesday, December 15, 11 am Place: Sala Seminari Est, Dipartimento di Informatica, Università di Pisa Title: CORSING: Sparse approximation of PDEs based on Compressed Sensing Abstract: We present a novel method for the numerical approximation of PDEs, motivated by recent developments in sparse representation, and particularly by compressed sensing. We named this approach CORSING (COmpRessed SolvING). Establishing an analogy between the sampling of a signal and the Petrov-Galerkin discretization of a PDE, the CORSING method can recover the best s-term approximation to the solution with respect to N suitable trial functions, with s<<N, by evaluating the bilinear form associated with the PDE against a randomized choice of m<<N test functions. This yields an underdetermined m x N linear system, that is solved by means of sparse optimization techniques. A theoretical analysis of the CORSING procedure is presented, based on the concepts of local a-coherence and restricted inf-sup property, along with numerical experiments that confirm the robustness and reliability of the proposed strategy. === Everyone is welcome! -- --federico poloni Dipartimento di Informatica, Università di Pisa http://www.di.unipi.it/~fpoloni/ tel:+39-050-2213143

1 0

Seminario di Dierk Schleicher
by Dario A. Bini 16 Oct '15

16 Oct '15

Speaker: Dierk Schleicher Title: Newton’s method as an unexpectedly efficient root finder Time: Friday, October 23; 10:00 Place: Aula Magna, Dipartimento di Matematica Abstract: Newton’s method is well known as a root finder locally near the roots. It is often “not recommended” as a global root finder because of its “chaotic” properties. We give a very efficient theoretical upper bound on its speed of convergence: all roots of a degree d polynomial can be found with accuracy eps in O(d^2 log^4 d + d log|\log eps|) Newton iterations in the expected case — very close to the theoretical upper bound of O(d^2) for this method. In practice, all roots of polynomials of degree more than a million are found routinely and in (4log 2) d^2 iterations — in practice, this means less than a day for degree a million on standard laptops. A modified method, for which we do not yet have a complete theory, brings this down to 3 d log^2 d iterations, which in practice for certain polynomials finds all roots of degree a million in a matter of minutes. === Everyone is welcome! Dario A. Bini

1 0

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

NumPI October 2015