December 2015 - NumPI - Mailing list — Dipartimento di Matematica, UniPI

Reminder: Optimization & Numerical Analysis seminars: Brugiapaglia
by Federico Poloni 20 Jun '16

20 Jun '16

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

2 8

[Dipartimento.di] Reminder: Optimization & Numerical Analysis seminars: Strabic
by Federico Poloni 18 Dec '15

18 Dec '15

Speaker: Nataša Strabić Affiliation: The University of Manchester Time: Wednesday, December, 9; h. 15:00 Place: Sala Seminari Ovest, Dipartimento di Informatica, Università di Pisa Title: Recent Progress on the Nearest Correlation Matrix Problem Abstract: In a wide range of applications it is required to replace an empirically obtained unit diagonal indefinite symmetric matrix with a valid correlation matrix (unit diagonal positive semidefinite matrix). A popular replacement is the nearest correlation matrix in the Frobenius norm. The first method for computing the nearest correlation matrix with guaranteed convergence was the alternating projections method proposed by Higham in 2002. The rate of convergence of this method is at best linear, and it can require a large number of iterations to converge to within a given tolerance. Although a faster globally convergent Newton algorithm was subsequently developed by Qi and Sun in 2006, the alternating projections method remains very widely used. We show that Anderson acceleration, a technique for accelerating the convergence of fixed-point iterations, can be applied to the alternating projections method and that in practice it brings a significant reduction in both the number of iterations and the computation time. We also show that Anderson acceleration remains effective, and indeed can provide even greater improvements, when it is applied to the variants of the nearest correlation matrix problem in which specified elements are fixed or a lower bound is imposed on the smallest eigenvalue. This is particularly significant for the nearest correlation matrix problem with fixed elements because no Newton method with guaranteed convergence is available for it. Both methods for computing the nearest correlation matrix are based on repeated eigenvalue decompositions and so they can be infeasible in time-critical situations. We have recently proposed an alternative method to restore definiteness to an indefinite matrix called shrinking. The method is based on computing the optimal parameter in a convex linear combination of the indefinite starting matrix and a chosen positive definite target matrix. We show how this problem can be solved by the bisection method and posed as a generalized eigenvalue problem, and we demonstrate how exploiting positive definiteness in these two methods leads to impressive computational savings. The work on these two topics is joint with Nicholas J. Higham, and, for shrinking, with Vedran Šego. === Everyone is welcome! -- --federico poloni Dipartimento di Informatica, Università di Pisa http://www.di.unipi.it/~fpoloni/ tel. +39 050 2213143 ______________________________________________ Dipartimento.di mailing list Dipartimento.di(a)listgateway.unipi.it http://listgateway.unipi.it/mailman/listinfo/dipartimento.di

2 1

[Dipartimento.di] Optimization & Numerical Analysis seminars: Strabic
by Federico Poloni 03 Dec '15

03 Dec '15

Speaker: Nataša Strabić Affiliation: The University of Manchester Time: Wednesday, December, 9; h. 15:00 Place: Sala Seminari Ovest, Dipartimento di Informatica, Università di Pisa Title: Recent Progress on the Nearest Correlation Matrix Problem Abstract: In a wide range of applications it is required to replace an empirically obtained unit diagonal indefinite symmetric matrix with a valid correlation matrix (unit diagonal positive semidefinite matrix). A popular replacement is the nearest correlation matrix in the Frobenius norm. The first method for computing the nearest correlation matrix with guaranteed convergence was the alternating projections method proposed by Higham in 2002. The rate of convergence of this method is at best linear, and it can require a large number of iterations to converge to within a given tolerance. Although a faster globally convergent Newton algorithm was subsequently developed by Qi and Sun in 2006, the alternating projections method remains very widely used. We show that Anderson acceleration, a technique for accelerating the convergence of fixed-point iterations, can be applied to the alternating projections method and that in practice it brings a significant reduction in both the number of iterations and the computation time. We also show that Anderson acceleration remains effective, and indeed can provide even greater improvements, when it is applied to the variants of the nearest correlation matrix problem in which specified elements are fixed or a lower bound is imposed on the smallest eigenvalue. This is particularly significant for the nearest correlation matrix problem with fixed elements because no Newton method with guaranteed convergence is available for it. Both methods for computing the nearest correlation matrix are based on repeated eigenvalue decompositions and so they can be infeasible in time-critical situations. We have recently proposed an alternative method to restore definiteness to an indefinite matrix called shrinking. The method is based on computing the optimal parameter in a convex linear combination of the indefinite starting matrix and a chosen positive definite target matrix. We show how this problem can be solved by the bisection method and posed as a generalized eigenvalue problem, and we demonstrate how exploiting positive definiteness in these two methods leads to impressive computational savings. The work on these two topics is joint with Nicholas J. Higham, and, for shrinking, with Vedran Šego. === Everyone is welcome! -- --federico poloni Dipartimento di Informatica, Università di Pisa http://www.di.unipi.it/~fpoloni/ tel. +39 050 2213143 ______________________________________________ Dipartimento.di mailing list Dipartimento.di(a)listgateway.unipi.it http://listgateway.unipi.it/mailman/listinfo/dipartimento.di

1 0