Joint CUNY Graduate Center-Courant
Seminar in Symbolic-Numeric Computing



    When and where


    Related events


    Upcoming talks

  1. Date: December 6, 2018, 3:30-4:30 pm

    Joe Kileel, Princeton University


    Title: Orbit retrieval, with applications to cryo-electron microscopy

    Abstract: In many problems in computer vision, robotics and image/signal processing, we wish to recover latent variables from observations suffering unknown shifts or rotations. One example is cryo-electron microscopy (cryo-EM), recognized by the Nobel Prize 2017 in Chemistry. Here the challenge is to estimate the 3D structure of a protein from many, very noisy 2D images taken at unknown viewing directions.

    In this talk, we place cryo-EM reconstruction inside a general framework for statistical estimation under noisy group actions — orbit retrieval. We show a tight relation between the sample complexity for orbit retrieval and the invariant theory of the underlying symmetry group. On the algebra side, this motivates apparently new questions in invariant theory and computational algebraic geometry — to which we offer partial algorithmic answers in general.

    Work-in-progress extending basic orbit retrieval is also presented, leading to specially structured problems in tensor decomposition and non-convex optimization. For the cryo-EM case, we validate our methodology on real data, in the context of ab initio modeling. Joint work with Amit Singer's group and Afonso Bandeira's group.

    Video broadcast is expected to be available here.


  2. Past talks

  3. Date: November 8, 2018, 3:30-4:30 pm

    Frank Sottile, Texas A&M University


    Title: Galois Groups for Systems of Equations

    Abstract: Camille Jordan observed that Galois groups arise in enumerative geometry, and we now also understand them as monodromy groups. A study of this question in the Schubert calculus has determined many such Galois groups, all known Schubert Galois groups are either the full symmetric group or are imprimitive. Recently, Esterov considered this question for systems of sparse polynomials and proved this dichotomy in that setting. While this classification identifies polynomial systems with imprimitive Galois groups, it does not identify the groups.

    I will sketch the background, before explaining Esterov's classification and ongoing work identifying some of the imprimitive Galois groups for polynomial systems.

    Video recording is available here.


  4. Date: October 18, 2018, 3:30-4:30 pm

    Konstantin Mischaikow, Rutgers University


    Title: A Combinatorial/Algebraic Topological Approach to Nonlinear Dynamics

    Abstract: Motivated by the increase in data driven science I will discuss a combinatorial/algebraic topological approach to characterizing nonlinear dynamics. In particular, I will describe how order theory can be used to efficiently and effectively organize the decomposition of dynamics and propose a definition of nonlinear dynamics based on these structures. I will then argue that algebraic topological tools such as the Conley index can be used to identify classical dynamical structures. Throughout I will focus on the computability of this approach as this is essential for applications.

    Depending on time I will conclude with specific examples associated with gene regulatory networks.

    Video recording is available here.


  5. Date: September 27, 2018

    Thomas Kahle, University Magdeburg


    Title: The geometry of gaussoids

    Abstract: Gaussoids are combinatorial structures that encode independence in probability and statistics, just like matroids encode independence in linear algebra. We show that the gaussoid axioms of Lnenicka and Matus are equivalent to compatibility with certain quadratic relations among principal and almost-principal minors of a symmetric matrix. This approach facilitates insights into symmetry and realizability of gaussoids as well as several extensions (like oriented, positive, and valuated gaussoids).

    This is based on joint work with T. Boege, A. D'Ali, and B. Sturmfels.

    Video recording is available here.


  6. Date: September 13, 2018

    Mike Shub, CUNY City College


    Title: The P versus NP problem and the Tau conjecture

    Abstract: I will survey some results concerning the P versus NP problem in various contexts including arithmetic with round-off errors. The relationship to the problem over the complex numbers with the Tau conjecture will be explained. The Tau conjecture states that there is a constant c such that if f is an integral polynomial generated from 1 and t by k additional operations in the ring Z[t], then f has at most (k+1)c distinct integer roots.

    Video recording is available here.

  7. Date: Friday, September 7, 2018, room 5382, time: 10-11 am

    Stephen Melczer, University of Pennsylvania


    Title: Symbolic Computation and Analytic Combinatorics in Several Variables

    Abstract: The field of analytic combinatorics in several variables (ACSV) is at the forefront of computational combinatorics - a subject dedicated to computability and complexity questions in enumeration. Drawing from singularity theory, computational topology, and algebraic geometry, ACSV raises a wide range of interesting computer algebra questions. This talk will survey ACSV from a computer algebra viewpoint, discuss current work, and highlight remaining open problems and generalizations.

    Video recording is available here.

  8. Date: September 6, 2018

    Manuel Kauers, Johannes Kepler University


    Title: Onsager's solution of the Ising model could have been guessed

    Abstract: In the 1940s, Onsager found a closed form solution for the free energy in the 2D square Ising model without magnetic field. His formula is celebrated as one of the greatest scientific achievements of the 20th century. Although the derivation has been considerably simplified during the past decades, even the simplest derivation known today is not simple. In the talk, we will present a simple non-rigorous derivation of Onsager's formula starting from knowledge that was available to Onsager and using modern computer algebra, which Onsager of course did not have. This is joint work with Doron Zeilberger (arXiv:1805.09057).

    Slides of the talk are available here.

  9. Date: August 30, 2018

    Jose Rodriguez, University of Chicago


    Title: Algebraic methods for point estimation

    Abstract: In statistics, point estimation uses sample data to calculate the "best estimate" of an unknown population parameter. For example, the sample average can be used to estimate the population mean. While there are many different point estimators, some of the most common ones are the maximum likelihood estimator (MLE), method of moments, and generalized method of moments (GMM).

    Algebraic statistics studies statistical models through the lens of algebra, geometry, and combinatorics. From model selection to inference, this interdisciplinary field has seen applications in a wide range of statistical procedures. In this talk, I will review maximum likelihood estimation and the maximum likelihood degree (ML degree) for discrete models. In particular, I will say how the maximum likelihood degree gives a measure of the algebraic complexity of the point estimate for MLE. Next, I will show how the monodromy homotopy method can be used to determine a point estimate. Moreover, if time permits, I will also discuss ongoing work regarding the algebraic degree of GMM. There will be illustrative examples throughout the talk, and a background in algebra will not be assumed.

    Video recording is available here.


  10. Date: Friday, May 11, 2018, room 5382, time: 2-3 pm

    Julio Banga, Marine Research Institute, Vigo


    Title: Optimality principles and identification of dynamic models of biosystems

    Abstract: Deterministic nonlinear ODEs are widely used in computational systems biology. The inverse problem of parameter estimation can be very challenging and has received great attention. Here, we will discuss a generalization of this problem which addresses the following question: given a dynamic model and observed time-series data, estimate the time-invariant model parameters, the unmeasured time-dependent inputs and the underlying optimality principle that is consistent with the measurements. We will justify the use of optimality principles in this context, and we will present an inverse optimal control formulation that can be used to solve the above problem under some assumptions. We will also discuss associated identifiability issues, and how to surmount them in special cases. We will illustrate these ideas with examples of increasing complexity involving metabolic and signaling pathways.

    Video recording is available here.

    Slides of the talk are available here.

  11. Date: Friday, May 11, 2018, room 5382, time: 3-4 pm

    Hoon Hong, NC State University


    Title: Deciding consistency of real polynomial constraints by prolongation and relaxation

    Abstract: The combination of prolongation and relaxation is a fundamental technique for reducing a difficult problem to a larger but easier problem.

    It has been successfully applied to checking the consistency of polynomial equations over complex numbers by Sylvester and Macaulay, reducing it to that of linear equations. It has been also successfully applied to differential equations by Kolchin, reducing it to that of polynomial equations.

    In this talk, we share our on-going effort on applying the technique to polynomial equations/inequalities over real numbers, reducing it to that of linear equations/inequalities.

    This is a joint work with Brittany Riggs.

    Video recording is available here.


  12. Date: May 10, 2018

    Amaury Pouly, Max Planck Institute, Saarbrücken


    Title: Computational complexity of solving polynomial differential equations over unbounded domains

    Abstract: In this talk, I will present a rigorous numerical algorithm which solves initial-value problems defined with polynomial differential equations (i.e. initial-value problems of the type y'=p(t,y), y(t0)=y0, where p is a vector of polynomials) for any value of t. The inputs of the algorithm are the data defining the initial-value problem, the time T at which we want to compute the solution of the IVP, and the maximum allowable error ε>0. Using these inputs, the algorithm will output a value YT such that |YT-y(T)|. The main contribution of this algorithm is to take all parameters of the problem into account in the complexity. To do so, we need to introduce a parameter, namely the length of the solution curve, to obtain a good complexity bound. I will discuss the implication of this bound and how this is a step toward a more "geometrical" measure of the complexity of the problem.

    Video recording is available here.

    Slides of the talk are available here.

  13. Date: May 3, 2018

    Rémi Imbach, New York University


    Title: Numerical and certified computation of the topology of projected curves

    Abstract: We consider plane curves obtained by projecting algebraic or analytic space curves. Such a curve is not smooth, and computing its singularities and more generally its topology is a challenging problem that is of particular interest when designing the mechanic of a parallel robot, or when studying a parameterized system of equations. State of the art approaches to compute the topology of algebraic plane curves use symbolic calculus. When the considered curve is obtained by projection, its representation as a resultant polynomial makes the latter approaches very costly, even for curves with low degree.

    It is however possible to use numerical methods with guarantees of results to address the considered problem. We will present two characterizations of the singularities as regular solutions of a square system of equations. The first one uses sub-resultant chain; the second one avoids the use of resultant and can be applied to projected analytic curves. A solver using multi-precision interval arithmetic and subdivision has been designed to compute the solutions of the systems characterizing the singularities.

    Then we will present a global and geometric approach to compute the topology of a projected curve, by computing a graph and one of its embedding that is isotopic to the projected curve. in order to achieve this we compute numerically a certified approximation of the space curve both to ease the research of singularities and to compute smooth branches linking singularities.

    Video recording is available here.

  14. Date: April 26, 2018

    Thomas Ligon, Ludwig Maximilian University of Munich


    Title: Programming MATLAB Symbolic Math Toolbox for Speed: Experience from the GenSSI Version 2 Project

    Abstract: Dynamical systems, especially in systems biology, are often modeled by systems of ordinary differential equations (ODEs) and we want to know if it is possible to infer the parameters of these equations (e.g. reaction rates) from experimental data, in a process called parameter estimation or "the inverse problem". If this is possible in principle, i.e. based on optimal data, the parameters are called "structurally identifiable". GenSSI (Generating Series for testing Structural Identifiability) uses generating series of Lie derivatives to analyze the structural identifiability of parameters of a set of ODEs based on arbitrary analytical functions. We converted GenSSI from version 1, which uses the Maple toolbox and runs on MATLAB version R2008a and older, to version 2, which uses the MATLAB Symbolic Math toolbox (based on MuPAD) and runs on MATLAB version R2008b and newer. As part of this, we corrected some very significant performance issues with the Symbolic Math toolbox, ultimately achieving better performance than the original version. This talk addresses those performance aspects.

    Video recording is available here.

    Slides of the talk are available here.

  15. Date: April 19, 2018

    André Platzer, Carnegie Mellon University


    Title: Logic & Proofs for Cyber-Physical Systems

    Abstract: Cyber-physical systems (CPS) combine cyber aspects such as communication and computer control with physical aspects such as movement in space, which arise frequently in many safety-critical application domains, including aviation, automotive, railway, and robotics. But how can we ensure that these systems are guaranteed to meet their design goals, e.g., that an aircraft will not crash into another one?

    This talk highlights some of the most fascinating aspects of cyber-physical systems and their dynamical systems models, such as hybrid systems that combine discrete transitions and continuous evolution along differential equations. Because of the impact that they can have on the real world, CPSs deserve proof as safety evidence.

    Multi-dynamical systems understand complex systems as a combination of multiple elementary dynamical aspects, which makes them natural mathematical models for CPS, since they tame their complexity by compositionality. The family of differential dynamic logics achieves this compositionality by providing compositional logics, programming languages, and reasoning principles for CPS. Differential dynamic logics, as implemented in the theorem prover KeYmaera X, have been instrumental in verifying many applications, including the Airborne Collision Avoidance System ACAS X, the European Train Control System ETCS, automotive systems, mobile robot navigation, and a surgical robot system for skull-base surgery. This combination of strong theoretical foundations with practical theorem proving challenges and relevant applications makes Logic for CPS an ideal area for compelling and rewarding research.

    Video recording is available here.

    Slides of the talk are available here.

  16. Date: Friday, March 2, 2018, 2-3:30 pm, room 5382

    Anne Shiu, Texas A&M University


    Title: Identifiability of linear compartment models: the singular locus

    Abstract: This talk addresses the problem of parameter identifiability – that is, the question of whether parameters can be recovered from data – for linear compartment models. Using standard differential algebra techniques, the question of whether such a model is (generically, locally) identifiable is equivalent to asking whether the Jacobian matrix of a certain coefficient map, arising from input-output equations, is generically full rank. A formula for these input-output equations was given recently by Meshkat, Sullivant, and Eisenberg. Here we build on their results by giving a formula for the resulting coefficient maps. This formula is in terms of acyclic subgraphs of the directed graph underlying the linear compartment model. As an application, we prove that two families of linear compartment models – cycle and mammillary (star) models – are identifiable. We accomplish this by determining the defining equation for the singular locus of non-identifiable parameters. Our work helps to shed light on the open question of which linear compartment models are identifiable. This is joint work with Elizabeth Gross and Nicolette Meshkat.

    Video recording is available here.

    Slides of the talk are available here.

  17. Date: November 9, 2017, 3-4 pm

    Reinhard Laubenbacher, University of Connecticut


    Title: Finite Dynamic Networks

    Abstract: A finite dynamic network is a special type of function from a finite set to itself, constructed from a directed graph. Dynamics is generated by iteration of the function, and is captured by its state space graph, which has as nodes the elements of the set, and directed edges that indicate the action of the function. Such dynamic networks have been used in a variety of contexts for the modeling of dynamic processes, in particular in systems biology, where they appear in the form of, e.g., Boolean network models of gene regulatory networks. One fundamental problem in the study of dynamic networks and their applications is to derive properties of the state space graph from properties of the set and the structure of the function, for instance steady states and periodic attractors, without actually computing the entire state space graph. In general, this is of course not possible, so additional assumptions on the function are needed. Biology provides one source of such assumptions, in particular the theory of "canalization," first postulated in developmental biology. This talk will present the outlines of a program to address this fundamental problem and some initial results. There are several possible approaches. Here, a formalization of the problem in the context of computational polynomial algebra over finite fields is discussed.

    Video recording is available here.


  18. Date: October 19, 2017, 3-4 pm

    Simon Foucart, Texas A&M University


    Title: Computing a quantity of interest from observational data

    Abstract: Scientific problems often feature observational data received in the form w1=l1(f),...,wm=lm(f) of known linear functionals applied to an unknown function f from some Banach space X, and it is required to either approximate f (the full approximation problem) or to estimate a quantity of interest Q(f). In typical examples, the quantities of interest can be the maximum/minimum of f or some averaged quantity such as the integral of f, while the observational data consists of point evaluations. To obtain meaningful results about such problems, it is necessary to possess additional information about f, usually as an assumption that f belongs to a certain model class K contained in X. This is precisely the framework of optimal recovery, which produced substantial investigations when the model class is a ball of a smoothness space, e.g. when it is a Lipschitz, Sobolev, or Besov class. This presentation is concerned with other model classes described by approximation processes. Its main contributions are:

    (i) for the estimation of quantities of interest, the production of numerically implementable algorithms which are optimal over these model classes,

    (ii) for the full approximation problem, the construction of linear algorithms which are optimal or near optimal over these model classes in case of data consisting of point evaluations.

    Regarding (i), when Q is a linear functional, the existence of linear optimal algorithms was established by Smolyak, but the proof was not numerically constructive. In classical recovery settings, it is shown here that such linear optimal algorithms can be produced by constrained minimization methods, and examples involving the computations of integrals from the given data are examined in greater details.

    Regarding (ii), it is shown that linearization of optimal algorithms can be achieved for the full approximation problem, too, in the important situation where the lj are point evaluations and X is a space of continuous functions equipped with the uniform norm. It is also revealed how the quasi-interpolation theory allows for the construction of linear algorithms which are near optimal.

  19. Date: August 31, 2017, 3-4 pm

    Nikki Meshkat, Santa Clara University


    Title: Structural Identifiability of Biological Models

    Abstract: Parameter identifiability analysis addresses the question of which unknown parameters of a model can be determined from given input-output data. In this talk, we discuss structural identifiability analysis, which addresses whether or not the model parameters can be determined from perfect input-output data (noise-free and of any duration required) and is an important step in the parameter estimation problem. Many linear ODE models used in systems biology are unidentifiable, which means that parameters can take on an infinite number of values and yet yield the same input-output data. We study a particular class of unidentifiable models and find conditions to obtain identifiable reparametrizations of these models. In particular, we use a graph-theoretic approach to analyze the models and show that graphs with certain properties allow a monomial scaling reparametrization over identifiable functions of the parameters. We also examine conditions to obtain identifiability for this class of models, and in particular, show how identifiability can be determined by simply looking at the graphical structure of these linear compartmental models.

    Video recording is available here and here (slides with audio recording). The slides in PDF are here.

  20. Date: May 11, 2017, 3-4 pm

    Xianfeng David Gu, SUNY Stony Brook


    Title: Discrete Surface Ricci Flow and Optimal Mass Transportation

    Abstract: In engineering and medical applications, it is crucial to find angle-preserving and area-preserving mappings. Discrete surface Ricci flow theory offers a practical tool to solve the first problem, discrete optimal mass transportation theory can be applied to solve the second one. In this talk, we introduce the theory, algorithm for both theories, and briefly introduce their applications in engineering fields.

  21. Date: April 6, 2017, 1:30-3:30 pm

    Liang Zhao, CUNY Graduate Center


    Title: Fast algorithms on random matrices and structured matrices

    Abstract: Randomization of matrix computations has become a hot research area in the big data era. Sampling with randomly generated matrices has enabled fast algorithms to perform well for some most fundamental problems of numerical algebra with probability close to 1. The dissertation develops a set of algorithms with random and structured matrices for the following applications:

    1) We prove that using random sparse and structured sampling enables rank-r approximation of the average input matrix having numerical rank r.

    2) We prove that Gaussian elimination with no pivoting (GENP) is numerically safe for the aver- age nonsingular and well-conditioned matrix preprocessed with a nonsingular and well-conditioned f-Circulant or another structured multiplier. This can be an attractive alternative to the customary Gaussian elimination with partial pivoting (GEPP).

    3) By using structured matrices of a large family we compress large-scale neural networks while retaining high accuracy. The results of our extensive are in good accordance with those of our theoretical study.

  22. Date: March 30, 2017, 2-4 pm

    James Davenport, University of Bath


    Title: The 'doubly-exponential' problem in equation/inequality solving

    Abstract: It is well-known that the degrees of Gröbner Bases are doubly exponential in the number of variables [MayrMeyer1982]. Similarly, real quantifier elimination can be doubly exponential in the number of variables [DavenportHeintz1988]. Recent results show that Gröbner bases are only doubly exponential in the dimension, not the actual number of variables. In joint with with Matthew England, we have shown that the double exponent in real quantifier elimination can be reduced by the number of equations, provided that the equations (and their iterated resultants) are content-free. We will explain these results, and why the proviso is necessary. We will also introduce the algorithm LazyRealTriangularize [Chen et al., 2013a], which in practice seems to have good behaviour, though there is no theoretical analysis.

    Slides of the talk are available here.

  23. Date: March 23, 2017, 2-4 pm

    Daniel Roche, United States Naval Academy


    Title: Pattern matching, X+Y, and Sparse Multiplication

    Abstract: The pattern matching problem is about finding a search pattern (possibly with wildcard characters) within a larger text, and has applications ranging from music retrieval to genetics. The X+Y problem is a basic algorithmic puzzle: given two sets of integers X and Y, find all sums (x+y) between the elements of the two sets. Finally, sparse polynomial multiplication is the problem of determining the product of two multivariate polynomials, where only the nonzero terms of the input and output are explicitly stored.

    On the surface, these problems are entirely unrelated. But they all share an important similarity from a computational point of view: in the worst case, they require quadratic running time, but in many cases the size of the output is significantly less than the worst-case bound suggests. This happens because of overlapping matches in pattern matching, repeated sums in X+Y, or colliding terms in polynomial multiplication. So it is reasonable to seek output-sensitive algorithms, whose running time decreases when the output size is small.

    As it turns out, the core to solving all three problems comes from recent advances in sparse polynomial interpolation, that is, discovering a formula for an unknown polynomial after sampling it at a small number of chosen points. We will outline the connection between each of these important problems and sparse interpolation, and present a randomized algorithm to compute the answer to all three in "nearly linear" expected running time.

  24. Date: March 16, 2017, 3:05-4 pm

    Michael Sagraloff, Max-Planck-Institut für Informatik


    Title: A polynomial-time algorithm for computing real roots of sparse polynomials

    Abstract: In this talk, I will consider the problem of computing the real roots of a sparse univariate polynomial f with arbitrary real (complex) coefficients. Here, we assume the existence of an oracle that provides arbitrary good approximations of the non-zero coefficients of f. For dense polynomials, there exist quite efficient methods to isolate and further approximate the roots of f, however these methods are not sparsity aware, and thus cannot be considered to be efficient if the number k of non-zero coefficients is considerably smaller than the degree n of f.

    Based on our previous work on computing the real/complex roots of a (dense) univariate polynomial, we propose an algorithm that, for a given integer L, returns disjoint disks Di in the complex space and corresponding positive integers mi such that each disk Di is centered at the real axis, has radius less than 2-L, and contains exactly mi roots of f counted with multiplicity. The sum of all mi is upper bounded by 2k and, in addition, each real root of f is contained in one of the disks. Hence, our algorithm computes (absolute) L-bit approximations of all real roots but may also return approximations of some non-real roots with small imaginary part.

    We show that the bit complexity of our algorithm is polynomial in k and log n, and even near-linear in L and τ, where 2 and 2τ constitute lower and upper bounds on the absolute values of the non-zero coefficients of f, respectively. If f has only simple real roots, our algorithm can also be used to isolate all real roots, in which case the bit complexity is polynomial in k and log n, and near-linear in τ and -log(s), where s denotes the separation of f. For the problem of isolating the real roots of a very sparse polynomial f with integer coefficients, our method performs near-optimal.

  25. Date: November 17, 2016. Special time: 4:10-5:30 pm

    Hoon Hong, NC State University


    Title: Root Separation Bound

    Abstract: Let f be a square-free polynomial. The root separation of f is the minimum of the pair-wise distance between the complex roots of f. Finding a lower bound on the root separation is a fundamental problem, arising in numerous disciplines. Due to its importance, there has been extensive research on this problem, resulting in various bounds. In this talk, we present another bound, which is "nicer" than the previous bounds in that

    (1) It is bigger (hence better) than the previous bounds.

    (2) It is covariant under the scaling of the roots, unlike the previous bounds.

    If time allows, we will also describe a generalization to multivariate polynomials systems.

    This is a joint work with Aaron Herman and Elias Tsigaridas.

    Video recording is available here, here, here, and here.


  26. Date: November 10, 2016. Special time: 4:10-5:30 pm

    Wen-shin Lee, University of Antwerp


    Title: Sparse interpolation, exponential analysis, Padé approximation and tensor decomposition

    Abstract: A common underlying problem statement in many applications is that of determining the number of components, and for each component the value of the frequency, damping factor, amplitude and phase in a multi-exponential model. It occurs, for instance, in magnetic resonance and infrared spectroscopy, vibration analysis, seismic data analysis, electronic odour recognition, keystroke recognition, nuclear science, music signal processing, transient detection, motor fault diagnosis, electrophysiology, drug clearance monitoring and glucose tolerance testing, to name just a few.

    We indicate the connections between sparse interpolation, generalized eigenvalue computation, exponential analysis, rational approximation, orthogonal polynomials and tensor decomposition. In the past few years, insight gained from the computer algebra community combined with methods developed by the numerical analysis community, has lead to significant progress in several very practical and real-life signal processing applications. We make use of tools such as the singular value decomposition and various convergence results for Padé approximants to regularize an otherwise inverse problem. Classical resolution limitations in signal processing with respect to frequency and decay rates, are overcome.

    Video recording is available here and here


  27. Date: May 5, 2016.

    Michael Burr, Clemson University


    Title: An Introduction and Recent Advances on Continuous Amortization

    Abstract: Continuous amortization was recently introduced as a technique to compute the complexity of subdivision-based algorithms.  This technique has been successfully applied, as a uniform technique, for computing the complexity of common root isolation algorithms. Continuous amortization can be used to compute many complexity-based quantities of subdivision-based algorithms, such as the number of subdivisions, the bit complexity, or the expected time.  Moreover, the complexity resulting from continuous amortization is based on the intrinsic geometric complexity of the input instance.  In practice, continuous amortization can be applied uniformly to a variety of algorithms and provides state-of-the-art results which are adaptive to the input data.  In the first part of this talk, I will provide an introduction to the continuous amortization technique, illustrating its application to various subdivision-based algorithms for isolating the solutions of polynomials. In the second part of this talk, I will discuss new work on the application of continuous amortization to problems in higher dimensions.

    Video recording is available here.


  28. Date: March 17, 2016.

    Dan Bates, Colorado State University


    Title: Numerical methods for investigating parameter spaces for parameterized polynomial systems

    Abstract: Various problems from mathematics and other disciplines can be formulated as parameterized polynomial systems. The problems then boil down to finding points of interest in the corresponding parameter space. For example, in the case of exceptional mechanism design, the problem is to find points in some parameter space for which the corresponding polynomial system has a solution set of dimension higher than that at almost all other points. For biochemical reaction networks, the problem is to catalog the set of chambers in the complement of a discriminant locus (where the number of real solutions is constant over each chamber). In this talk, I will introduce a few such problems from applications and some of the methods and software that have been developed in recent years to solve these problems, including at least Paramotopy (software for parameter homotopies) and fiber product methods.

    Video recording is available here.

    Slides of the talk are available here.


  29. Date: March 10, 2016.

    George Labahn, University of Waterloo


    Title: Symbolic-Numeric Computation with Rational Functions

    Abstract: To our knowledge, there appear to be very few results on numerical analysis with rational functions. Even for the simple question of how to measure the distance between two rational functions there are only few answers in the literature. However, for some applications like Padé approximants one desires rational functions without spurious poles. By this we mean one should not have small residuals in a partial fraction decomposition nor Froissart doublets consisting of a close-by pole and zero. As such we require measures of a rational function away from those potentially having spurious poles. We will point out the link with numerical GCD computations, see for instance (Beckermann, Labahn & 1998), and the singular values of underlying structured matrices (Corless, Gianni, Trager, Watt, 1995). It also turns out that the spherical derivative of the rational function can be a useful indicator.

    Joint work with Bernd Beckermann and Ana Matos.

    Video recording is available here and here



  30. Date: February 4, 2016.

    Jonathan Hauenstein, University of Notre Dame


    Title: Computing real solutions to systems of polynomial equations using numerical algebraic geometry

    Abstract: In many applications, the real solutions are of most interest to practitioners. For example, the mobility of a mechanism is associated with the dimension of the real solution set. This talk will explore various approaches in numerical algebraic geometry to compute and analyze the real solution set. Some examples include critical-point methods, cell decompositions, numerical local irreducible decompositions, and validation of a complete solution set using sums of squares programming. A collection of these techniques will be discussed in relationship to solving problems from enumerative geometry, mechanical engineering, and theoretical chemistry.

    Video recording is available here.



  31. Date: November 20, 2015. Time: 1 - 1:55 pm. Room: 5382 (note the time and room number)

    Saugata Basu, Purdue University


    Title: Complexity of constructible sheaves

    Abstract: Constructible sheaves play an important role in several areas of mathematics, most notably in the theory of D-modules. It was proved by Kashiwara and Schapira that the category of constructible sheaves is closed under the standard six operations of Grothendieck. This result can be viewed as a far reaching generalization of the Tarski-Seidenberg principle in real algebraic geometry. In this talk I will describe some quantitative/effectivity results related to the Kashiwara-Schapira theorem - mirroring similar results for ordinary semi-algebraic sets which are now well known. For this purpose, I will introduce a measure of complexity of constructible sheaves, and bound the complexity of some of the standard sheaf operations in terms of this measure of complexity. I will also discuss quantitative bounds on the dimensions of cohomology groups of constructible sheaves in terms of their complexity, again extending similar results on bounding the the ordinary Betti numbers of semi-algebraic sets.

    Slides of the talk are available here.

    Video recording is available here: Part 1, Part 2.


  32. Date: November 12, 2015

    Anton Leykin, Georgia Institute of Technology


    Title: Numerical Algebraic Geometry for schemes

    Abstract: I will review of basic concepts of Numerical AG used to describe complex algebraic varieties (reduced affine schemes) by approximate data computed with numerical methods. Then we will ponder a harder question: How can one describe a nonreduced affine scheme, a scheme where components may occur with multiplicities and embedded components may be present?

    Robert Krone spoke in this seminar about our joint work on an embedded component test — I will argue that this is an important step on the way to answering the above question.

    Audio recording is available here.

    Images of the blackboard are: Part 1, Part 2, Part 3, Part 4.


  33. Date: September 24, 2015

    Agnes Szanto, NC State University


    Title: Symbolic-Numeric Certification of Overdetermined and Singular Polynomial Systems

    Abstract: This talk is concerned with certifying that a given point is near an exact root of an overdetermined or singular polynomial system with rational coefficients. The difficulty lies in the fact that consistency of overdetermined systems is not a continuous property. Our certification is based on hybrid symbolic-numeric methods.

    This is a joint work with Tulay Akoglu, Jonathan Hauenstein and Bernard Mourrain.

    Video recording is available here.



  34. Date: September 17, 2015

    Erich Kaltofen, NC State University


    Title: Hybrid symbolic-numeric computation: a marriage made in heaven

    Abstract: Hybrid algorithms use floating point arithmetic for speed and symbolic computation for the type of objects: formulas and exact identities and inequalities.

    New hybrid algorithms are presented: for solving optimization problems by sum-of-squares proofs; for computing a sparse interpolant in power or Chebyshev basis via linear progressions. There, we allow for errors in the inputs, performing error-correction by methods from digital error correcting codes.

    Joint with Andrew Arnold, Clement Pernet, Zhengfeng Yang, Lihong Zhi.

    Video recording is available here and here.


  35. Date: August 27, 2015

    Robert Krone, Queen's University


    Title: Numerical primary decomposition

    Abstract: Finding a primary decomposition of a polynomial ideal is a hard computational problem. There are effective symbolic algorithms, but they can be slow in practice. For problems over the complex numbers, numerical primary decomposition offers a new strategy that builds on the previous success of other numerical algebraic geometry algorithms. I will outline this approach. Our main contribution is an algorithm for determining if a specified point lies on an embedded component of an affine ideal or not. We use local dual space computations to determine information about the local Hilbert function of the ideal at the point in question. This is joint work with Anton Leykin.

    Video recording is available here and here.


  36. May 14, 2015

    Éric Schost, University of Western Ontario

    A Monte Carlo algorithm for the symbolic solution of polynomial systems in [X,Y]

    Abstract: We give an algorithm for the symbolic solution of polynomial systems in [X,Y]. Following previous work with Lebreton, we use a combination of lifting and modular composition techniques, relying in particular on Kedlaya and Umans' recent quasi-linear time modular composition algorithm.

    Our main contribution is an adaptation of a deflation algorithm of Lecerf's, that allows us to treat singular solutions for essentially the same cost as the regular ones. Altogether, for an input system with degree d and coefficients of bit-size h, we obtain Monte Carlo algorithms with running time d3+ε O~(d+h) bit operations, for any ε > 0.

    The slides of the talk are available here.


  37. April 23, 2015, room 4102, 3:15 - 4:50 pm

    Mark Giesbrecht, University of Waterloo

    This seminar is joint with the Computer Science Colloquium

    Approximate Computation with Differential Polynomials: Approximate GCRDs, 3:15 - 4:00 pm

    Abstract: Differential (Ore) type polynomials with approximate polynomial coefficients are introduced. These provide a useful representation of approximate linear differential operators with a strong algebraic structure, which has been used very successfully in the exact, symbolic, setting.

    As an entrée to this framework, we present an algorithm for the approximate Greatest Common Right Divisor (GCRD) of two approximate differential polynomials. The GCRD is intuitively the linear differential operator whose solutions are those common to the two input operators. More formally, given approximate differential polynomials f and g, we investigate the problem of finding "nearby" polynomials f^ and g^ which have a non-trivial GCRD. Here "nearby" is under an appropriately defined coefficient 2-norm. We prove that the problem is well-defined (i.e., nearest polynomials with a GCRD exist), and explore algorithms to compute an approximate GCRD. We work on an appropriately "linearized" differential Sylvester matrix, and extend methods for the approximate GCD of regular polynomials to this new setting, including SVD-based methods and Newton iteration.

    This is joint work with PhD student Joseph Haraldson (Waterloo) and Erich Kaltofen (NCSU)



    Sparsity, Complexity and Practicality in Symbolic Computations, 4:05 - 4:50 pm

    Abstract: Modern symbolic computation systems provide an expressive language for describing mathematical objects. For example, we can easily enter equations such as

    f=x2100y2 + 2x299+1y299+1 +2x299y+y2100x2+2y299x+1

    into a computer algebra system. However, to determine the factorization

    f → (x299y+y299x+1)2

    with traditional methods would incur huge expression swell and high complexity. Indeed, many problems related to this one are provably intractable, or suspected to be so. Nonetheless, recent work has yielded exciting new algorithms for computing with sparse mathematical expressions. In this talk, we will attempt to navigate this hazardous computational terrain of sparse algebraic computation. We will discuss new algorithms for sparse polynomial root finding and functional decomposition. We will also look at the "inverse" problem of interpolating or reconstructing sparse mathematical functions from a small number of sample points. Computations over traditional symbolic domains, such as the integers and finite fields, as well as symbolic-numeric computations for approximate (floating point) data, will be considered. Fast algorithms should require time polynomial in the size of the sparse representation of the input and output, and will need to manage coefficient growth, intermediate expression swell, and numerical stability as appropriate to the problem.

    Video recording is available here and here.


  38. March 26, 2015

    Chee Yap, New York University

    Towards Soft Voronoi Diagrams

    Abstract: Voronoi diagrams give rise to extremely versatile data structures in many applications. New forms of Voronoi diagrams are constantly invented and studied, but some of these seems very hard to compute properly.

    For computational geometers, the standard computational model is the real RAM model. Within this model, the theory of Exact Geometric Computation tells us that all geometric relations can be reduced to evaluation of suitable exact ("hard") predicates. But for Voronoi diagrams (though this is not really unique to Voronoi diagrams), these hard predicates may be unknown, or have high complexity, or not known to be computable. To side step these issues, we are forced to consider approximate or "soft" predicates. This is no loss, as many applications are fine with soft solutions.

    But there are many challenges including the proper definition of soft Voronoi diagrams and designing truly soft algorithms. Our talk is illustrated with recent and ongoing work. This is a four point talk:

    1. Why we need to consider soft models
    2. A subdivision framework for soft algorithms
    3. Conceptual tools for soft computing
    4. Examples of soft Voronoi diagram algorithms

    Video recording is available here and here.


  39. February 26, 2015

    Robert Lewis, Fordham University


    Symbolic-Numeric Problems, Image Analysis, and Parametric Polynomial Systems

    Abstract: Systems of polynomial equations with parameters arise in many fields, such as geometric computing, flexibility of molecules, chemical reactions, game theory, operations research, and differential equations. Here we will focus on recent work with Bela Palancz and Joseph Awange on image analysis. Given a point cloud created by a laser scan, we want to discern underlying shapes. This entails separating "inliers" from "outliers" by the maximization of the likelihood function of a Gaussian mixture distribution. We will talk about trying to solve the resulting polynomial system with resultants and with Groebner bases.

    This is an applied talk with no mathematical theory beyond senior level undergraduate.

    Video recording is available here.

The seminar activities are partially supported by the National Science Foundation.


[Main page] [Mathematics seminars at CUNY] [Computer Science seminars at CUNY] [Contact the organizersContact the organizers]