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


    When and where


    Related events



  1. Date: Thursday, December 5, 2019, 2-4 pm

    Nicolas Brisebarre, École Normale Supérieure de Lyon

    Title: Correct rounding of transcendental functions: an approach via Euclidean lattices and approximation theory

    Abstract: On a computer, real numbers are usually represented by a finite set of numbers called floating-point numbers. When one performs an operation on these numbers, such as an evaluation by a function, one returns a floating-point number, hopefully close to the mathematical result of the operation. Ideally, the returned result should be the exact rounding of this mathematical value. If we’re only allowed a unique and fast evaluation (a constraint often met in practice), one knows how to guarantee such a quality of results for arithmetical operations like +,-,x,/ and square root but, as of today, it is still an issue when it comes to evaluate an elementary function such as cos, exp, cube root for instance. This problem, called Table Maker's Dilemma, is actually a diophantine approximation problem. It was tackled, over the last fifteen years, by V. Lefèvre, J.M. Muller, D. Stehlé, A. Tisserand and P. Zimmermann (LIP, ÉNS Lyon and LORIA, Nancy), using tools from algorithmic number theory. Their work made it possible to partially solve this question but it remains an open problem. In this talk, I will present an ongoing joint work with Guillaume Hanrot (ÉNS Lyon, LIP) that improve on a part of the existing results.

    Slides of the talk are available here.

    Video recording is available here.

  2. Date: Thursday, November 21, 2019, 2-3:45 pm, NYU, 60 Fifth Ave, room 446

    Rémi Imbach, New York University

    Title: Practical Advances in Complex Roots Clustering

    Abstract: We are interested in computing clusters of complex roots of polynomials and square polynomials systems. Root clustering differs of root isolation in that it can be performed softly, i.e. avoiding some decisions of zero. This allows clustering algorithms to be robust to multiple roots and to accept inputs given by black boxes for approximation, for instance polynomials which coefficients are roots of polynomials. The starting point of our talk is the existence of a clustering algorithm for roots of polynomials and its efficient implementation called Ccluster. We will show how this algorithm can be embedded in an algorithm for computing clusters of roots of triangular systems of polynomials resulting in particular of a symbolic step to process non-triangular systems. Back to the univariate case, we will present a new test for counting complex roots of a polynomial in a disk that can be particulary fast for polynomials that can be evaluated fast.

    Slides of the talk are available here.

    Video recording is available here.

  3. Date: Thursday, November 14, 2019, 2-4 pm, CUNY Graduate Center, room 3309

    Erich Kaltofen, North Carolina State University

    Title: Proof-of-work Certificates for High Complexity Computations for Linear Algebra

    Abstract: Computations done by high-power cloud servers such as a Google data center can yield outputs that are easy to verify, such as the factors of an integer, but outputs can also be non-trivial to certify quickly, such as the determinant of a high-dimensional sparse matrix like the Macaulay matrix or the summation of a very large number of consecutive prime numbers. Interactive proof protocols speed the complexity of the output verification by interaction between the high-power prover and the verifier, in fact, a polynomial-time verifier can certify all computational problems of PSPACE. The interaction can be removed to yield a proof-of-work certificate whose correctness is based on cryptographic assumptions on what the prover cannot ever compute. I will give a selection of certificates, among them our 2014 protocol for positive semidefiniteness of an integet matrix and our 2018 protocol for the rank profile of a matrix.

    Slides of the talk are available here.

    Video recording is available here.

  4. Date: Thursday, November 7, 2019, 2-4 pm, CUNY Graduate Center, room 3309

    Maurice Rojas, National Science Foundation and Texas A&M University

    Title: Fewnomial Hypersurfaces have Polynomially Many Connected Components

    Abstract: Suppose $A$ is a set of points in $\mathbb{R}^n$, of cardinality $n+k$, not all lying on the same affine hyperplane, and $c$ is a vector in $\mathbb{R}^{n+k}$ with no zero coordinates. The data $(A,c)$ naturally define an $n$-variate exponential sum $g$, with real coefficients and exactly $n+k$ terms, and such exponential sums generalize $n$-variate sparse polynomials. Let $Z$ be the zero of $g$ in $\mathbb{R}^n$. We prove that for generic $c$, $Z$ has \[O((n+k)^2 + 2^{(k^2)/2} n^{k-2})\] connected components. The best previous upper bound, counting just the unbounded connected components, was exponential in $n$, already in the special case $k=3$. Our bound is based on a more refined look at the singularities of $Z$ as $c$ varies along certain monomial curves in coefficient space, and makes use of a recent generalization of the $A$-discriminant (of Gelfand, Kapranov, and Zelevinsky) to exponential sums. This is joint work with Korben Rusek, and makes use of earlier joint work with Jens Forsgard and Mounir Nisse.

    Video recording is available here.

  5. Date: Thursday, October 31, 2019, 2-4 pm, CUNY Graduate Center, room 3309

    Dylan Peifer, Cornell University

    Title: Learning Selection Strategies in Buchberger's Algorithm

    Abstract: Buchberger's algorithm is the classical algorithm for computing a Gröbner basis, and highly-tuned and optimized versions are a critical part of many computer algebra systems. In practice, the time and space efficiency of Buchberger's algorithm strongly depends on the choice of a selection strategy which determines the order in which s-pair reductions are performed. Several basic strategies are used, but none are optimal, and the general problem of developing good selection strategies is difficult. Reinforcement learning provides a new framework for expressing and attacking this problem. In this talk we will review the concepts of selection strategies and reinforcement learning, phrase Buchberger's algorithm as a reinforcement learning problem, and apply policy gradient methods to learn new selection strategies that can match or beat the existing state-of-the-art.

    Slides of the talk are available here.

    Video recording is available here.

  6. Date: Friday, October 25, 2019, 2-3 pm, CUNY Graduate Center, room 5382

    Diego Armentano, Universidad de la República, Uruguay

    Title: Some Results on the Complexity of the Eigenvalue Problem

    Abstract: In this talk we will focus on the complexity of some algorithms designed for the eigenvalue problem. In particular we will present an algorithm for the eigenvalue(eigenvector) problem which runs on average polynomial time over the space of n by n complex matrices with Gaussian entries.
    (Joint work with C. Beltrán, P. Bürgisser, F. Cucker, and M. Shub.)

    Video recording is available here.

  7. Date: Thursday, October 24, 2019, 2-3:45 pm, NYU, 60 Fifth Ave, room 446

    Kisun Lee, Georgia Tech

    Title: Certifying solutions to a square analytic system

    Abstract: In this talk, we discuss about methods for proving existence and uniqueness of a root of a square analytic system in a given region. For a regular root, Krawczyk method and Smale's α-theory are used. On the other hand, when a system has a multiple root, there is a separation bound isolating the multiple root from other roots. We define a simple multiple root, a multiple root whose deflation process is terminated by one iteration, and establish its separation bound. We give a general framework to certify a root of a system using these concepts.

    Video recording is available here.

    Slides of the talk are available here.

  8. Date: Thursday, September 26, 2019, 2-4 pm, CUNY Graduate Center, room 6496

    Cleveland Waddell, Evergreen State College

    Title: Parametric Linear System Solving with Error Correction

    Abstract: Consider solving a black box linear system, A(u)x = b(u), where the entries are polynomials in u over a field K, and A(u) is full rank. The solution, x = f(u)/g(u), where g is always the least common monic denominator, can be recovered even if some evaluations are erroneous. In [Boyer and Kaltofen, Proc. SNC 2014] the problem is solved with an algorithm that generalizes Welch/Berlekamp decoding of an algebraic Reed-Solomon code. We describe an algorithm that given the same inputs uses possibly fewer evaluations to compute the solution. We also introduce a second count for the number of evaluations required to recover the solution based on work by Stanley Cabay. We give the criterion that determines when the Cabay count is fewer than the generalized Welch/Berlekamp count.

    The aforementioned algorithm does not work when the matrix of the system, A(u)x = b(u), is rank deficient and some evaluations cause errors. We next present an algorithm for solving black box linear systems where the entries are polynomials over a field and the matrix of the system is rank deficient.

    Our algorithm for parametric linear system solving can be specialized to the recovery of a vector of rational functions from its evaluations. We view the recovery of a vector of polynomials as the decoding of interleaved Reed-Solomon codes. It is known that interleaved schemes improve the error correction capabilities of codes when errors occur in bursts. If we consider that the evaluations of the polynomials in the vector are done one at a time and that the errors are dependent then it is likely that errors occur in consecutive evaluations (bursts). We show how to encode and transmit data (polynomials) on a burst channel so that the data (polynomials) transmitted can be recovered with fewer evaluations than is required by Generalized Welch/Berlekamp decoding.

    Video recording is available here.

    Slides of the talk are available here.

  9. Date: Thursday, May 30, 2019, 10:15-11:30 am, room 5382 (SPECIAL TIME AND LOCATION)

    Maria Pia Saccomani, University of Padova

    Title: Structural Identifiability of Rational ODE Models in Biological Systems: a real-world application of differential algebra

    Abstract: ODE models used to describe biological systems often depend on many unknown parameters. Structural identifiability concerns the uniqueness of the model parameters as determined from input-output data, under ideal conditions of noise-free observations. It is thus a prerequisite for parameter estimation to provide reliable and accurate results from experimental data. Often these ODE models consist of rational or even polynomial differential equations. In this context, the aims of this talk are

    1) to present a differential algebra method to test structural identifiability based on the structure of the characteristic set of the differential ideal generated by the polynomials defining the model,

    2) to explain the important role played by the model initial conditions in the characteristic set and the role of a system-theoretic property called accessibility, crucial to correctly check identifiability,

    3) to illustrate how one can combine our structural identifiability test with practical identifiability approaches in order to calculate either all the multiple parameter solutions of a locally identifiable model or, the analytic relations between the infinite number of solutions of a nonidentifiable model. These different solutions are equivalent to describe the observable input-output behaviour but they generally yield different dynamic behaviours of unmeasurable variables, whose prediction is often the main goal of mathematical modeling.

    The relevance of structural identifiability analysis in biological modeling is shown by some recent examples including HIV and oncological models. Structural identifiability is tested with our freely available software DAISY (Differential Algebra for Identifiability of SYstems).

    Video recording is available here.

    Slides of the talk are available here.


  10. Date: Thursday, May 23, 2019, 2-4 pm (SPECIAL TIME)

    Nathalie Verdière, University of Le Havre

    Title: Applications of computer algebra in the identifiability and diagnosability studies in nonlinear models

    Abstract: This talk adresses the use of computer algebra in the structural properties study of nonlinear dynamical models in particular, the identifiability and diagnosability properties. Identifiability answers the question of whether is it possible to uniquely recover the model parameters assuming noisy-free data. Since this property guarantees an unambiguous mapping between the model parameters and the output trajectories, it is considered as a necessary condition for successful parameter estimation from real, noisy data. Fault diagnosability study characterizes the faults that can be discriminated from the model using the available sensors in the biological/physical system. In this work, a fault is an unpermitted deviation of at least one parameter of the system from the acceptable standard condition. Since in our work faults correspond to parameter variations, the problem of diagnosability is closely related to the problem of identifiability. As it will be shown in this talk, computer algebra has proved to be very useful to highlight some specific properties of the system providing, in the same way, new tools to answer concrete questions.

    Video recording is available here.

    Slides of the talk are available here.

  11. Date: Thursday, March 28, 2019, 3-4 pm

    Danielle Brake, University of Wisconsin Eau Claire

    Title: Multiprecision: solving and causing problems

    Abstract: Systems of polynomials are not uniformly challenging to solve. Some are quite easy, others quite hard; and, what a statement of difficulty means depends on context including the solution method and output requirements. Numerical methods of solving systems typically produce inexact solutions, in the form of approximations using floating point numbers and a method of refining to arbitrary accuracy. Numerical algebraic geometry or numerical nonlinear algebra, uses probability-one arguments to theoretically justify algorithm aspects, such as choosing a random complex number for the infamous gamma trick. However, the floating point numbers are discrete and finite in number – there is no such thing as a probability-zero set in them! Furthermore, high condition numbers make some problems impossible to solve with built-in numeric types, such as 64-bit double. A cure is multiprecision, and it comes with a cost – and not just one in terms of longer time to compute. There are additional challenges to implementation of adaptive precision algorithms, including storage choices, type conversions, the spectre of mixed precision arithmetic, and the attracting wormhole of spaghetti code that awaits those who need to vary numeric type.

    Video recording is available here.

    Slides of the talk are available here.

  12. Date: Thursday, March 7, 2019, 3-4 pm

    Dan Roche, United States Naval Academy

    Title: Interactive Certificates for Polynomial Matrices with Sub-Linear Communication

    Abstract: We develop and analyze new protocols to verify the correctness of various computations on matrices over F[x], where F is a field. The properties we verify concern an F[x]-module and therefore cannot simply rely on previously-developed linear algebra certificates which work only for vector spaces. Our protocols are interactive certificates, often randomized, and featuring a constant number of rounds of communication between the prover and verifier. We seek to minimize the communication cost so that the amount of data sent during the protocol is significantly smaller than the size of the result being verified, which can be useful when combining protocols or in some multi-party settings. The main tools we use are reductions to existing linear algebra certificates and a new protocol to verify that a given vector is in the F[x]-linear span of a given matrix.

    This is joint work with David Lucas, Vincent Neiger, Clément Pernet, and Johan Rosenkilde.

    Video recording is available here.

    Slides of the talk are available here.

  13. Date: Friday, February 15, 2019, 2-3 pm, room 5382 (note special time, day, and room)

    Harm Derksen, University of Michigan

    Title: Singular Values of Tensors

    Abstract: Tensor decompositions have many applications, including chemometrics and algebraic complexity theory. Various notions, such as the rank and the nuclear norm of a matrix, have been generalized to tensors. In this talk I will present a new generalization of the singular value decomposition to tensors that shares many of the properties of the singular value decomposition of a matrix.

    Video recording is available here.

    Slides of the talk are available here.

  14. Date: Thursday, February 7, 2019, 3:30-4:30 pm, NYU Warren Weaver Hall, room 317 (note special location)

    Chee Yap, New York University

    Title: Isolating Simple Zeros of Systems of Equations, with Complexity Analysis

    Abstract: We describe a new algorithm for isolating the simple zeros of a function F:ℝn → ℝn within a box B0 in ℝn. The function F and its partial derivatives must have interval forms, but need not be polynomial. Our subdivision-based algorithm is "effective" in the sense that our algorithmic description also specifies the numerical precision that is sufficient to certify an implementation with any standard BigFloat number type. The main predicate is the Moore-Kioustelides (MK) test, based on Miranda's Theorem (1940). Although the MK test is well-known, this appears to be the first synthesis of this test into a complete root isolation algorithm. We provide a complexity analysis of our algorithm based on intrinsic geometric parameters of the system. Our algorithm and complexity analysis are developed using 3 levels of description (Abstract, Interval, Effective). This methodology provides a systematic pathway for achieving effective subdivision algorithms in general.

    Joint work with Xu Juan.

    Video recording is available here.

  15. 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 recording is available here.

    Slides of the talk are available here


  16. 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.


  17. 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.


  18. 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.


  19. 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.

  20. 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.

  21. 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.

  22. 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.


  23. 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.

  24. 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.


  25. 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.

  26. 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.

  27. 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.

  28. 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.

  29. 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.

  30. 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.


  31. 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.

  32. 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.

  33. 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.

  34. 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.

  35. 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.

  36. 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.

  37. 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.

  38. 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.


  39. 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


  40. 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.


  41. 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.


  42. 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


  43. 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.


  44. 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.


  45. 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.


  46. 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.


  47. 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.


  48. 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.


  49. 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.


  50. 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.


  51. 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.


  52. 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]