Events for 10/29/2018 from all calendars

Geometry Seminar

Time: 3:00PM - 4:00PM

Location: BLOC 628

Speaker: C. Ikenmeyer, Simons Inst. and Saarbruchen

Title: On Algebraic Branching Programs of Small Width

Abstract: In 1979, Valiant showed that the complexity class VF of families with polynomially bounded formula size is contained in the class VBP of families that have algebraic branching programs (ABPs) of polynomially bounded size. Motivated by the problem of separating these classes, we study the topological closure of VF, i.e., the class of polynomials that can be approximated arbitrarily closely by polynomials in VF. We describe this closure using the well-known continuant polynomial (in characteristic different from 2). Further understanding this polynomial seems to be a promising route to new formula size lower bounds. Our methods are rooted in the study of ABPs of small constant width. In 1992, Ben-Or and Cleve showed that formula size is polynomially equivalent to width-3 ABP size. We extend their result (in characteristic different from 2) by showing that approximate formula size is polynomially equivalent to approximate width-2 ABP size. This is surprising because in 2011 Allender and Wang gave explicit polynomials that cannot be computed by width-2 ABPs at all! The details of our construction lead to the aforementioned characterization of VF. This is joint work with Bringmann and Zuiddam.

Numerical Analysis Seminar

Time: 3:00PM - 4:00PM

Location: BLOC 624

Speaker: Agnieszka Miedlar, The University of Kansas

Title: The NLFEAST Algorithm for Large-Scale Nonlinear Eigenvalue Problems

Abstract: Eigenvalue problems in which the coefficient matrices depend nonlinearly on the eigenvalues arise in a variety of applications in science and engineering, e.g., dynamic analysis of structures or computational nanoelectronics, to mention just a few. This talk will discuss how the Cauchy integral-based approaches offer an attractive framework for using "spectrum slicing" to develop highly efficient and flexible techniques for solving large-scale nonlinear eigenvalue problems. We will first introduce the nonlinear counterpart of the well-established linear FEAST algorithm. Like its linear predecessor, the nonlinear FEAST (NLFEAST) algorithm can be used to solve nonlinear eigenvalue problems for the eigenpairs corresponding to eigenvalues that lie in a user-specified region in the complex plane, thereby allowing for the calculation of large number of eigenpairs in parallel. To develop a nonlinear FEAST algorithm that enables the iterative refinement of a subspace of a fixed dimension, we propose to use a modified form of the contour integral resulting from the relationship between the NLFEAST and the residual inverse iteration by Neumaier for the nonlinear eigenvalue problems. Finally, we will use several physically-motivated examples to illustrate the method. This is a joint work with B. Gavin, E. Polizzi and Y. Saad.

Industrial and Applied Math

Time: 4:00PM - 5:00PM

Location: BLOC 220

Speaker: Timo de Wolff, TU Berlin

Title: An Experimental Comparison of SONC and SOS Certificates for Unconstrained Optimization

Abstract: Finding the minimum of a multivariate real polynomial is a well-known hard problem with various applications. We present a polynomial time algorithm to approximate such lower bounds via sums of nonnegative circuit polynomials (SONC). As a main result, we carry out the first large-scale comparison of SONC, using this algorithm and different geometric programming (GP) solvers, with the classical sums of squares (SOS) approach, using several of the most common semidefinite programming (SDP) solvers. SONC yields bounds competitive to SOS in several cases, but using significantly less time and memory. In particular, SONC/GP can handle much larger problem instances than SOS/SDP. This is joint work with Henning Seidler.