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



    When and where


    Related events


    Upcoming talks

  1. Date: May 11, 2017, 2-4 pm

    Xianfeng David Gu, SUNY Stony Brook


    Title: TBA

    Abstract: TBA

    Video recording is expected to be available here.

  2. Past talks

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

    Video recording is available here.

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

    Video recording is available here.

    Slides of the talk are available here.

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

    Video recording is available here.

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

    Video recording is available here.

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

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

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

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

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


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


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

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


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



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


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


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

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


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


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