Susan Margulies

Efficient high-precision dense matrix algebra on parallel architectures for nonlinear discrete optimization

  • John Gunnels
  • Jon Lee
  • Susan Margulies
    • Categories Combinatorial Optimization, Graphs and Matroids, Parallel Algorithms Tags , , , , , , , , , ,

    We provide a proof point for the idea that matrix-based algorithms for discrete optimization problems, mainly conceived for proving theoretical efficiency, can be easily and efficiently implemented on massively-parallel architectures by exploiting scalable and efficient parallel implementations of algorithms for ultra high-precision dense linear algebra. We have successfully implemented our algorithm on the Blue Gene/L … Read more

    Hilbert’s Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility

  • Jesús A. De Loera
  • Jon Lee
  • Peter Malkin
  • Susan Margulies
    • Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization, Graphs and Matroids Tags , ,

    Systems of polynomial equations over an algebraically-closed field K can be used to concisely model many combinatorial problems. In this way, a combinatorial problem is feasible (e.g., a graph is 3-colorable, hamiltonian, etc.) if and only if a related system of polynomial equations has a solution over K. In this paper, we investigate an algorithm … Read more

    Expressing Combinatorial Optimization Problems by Systems of Polynomial Equations and the Nullstellensatz

  • Jesús A. De Loera
  • Jon Lee
  • Susan Margulies
  • Shmuel Onn
    • Categories Combinatorial Optimization, Integer Programming, Nonlinear Optimization Tags ,

    Systems of polynomial equations over the complex or real numbers can be used to model combinatorial problems. In this way, a combinatorial problem is feasible (e.g. a graph is 3-colorable, hamiltonian, etc.) if and only if a related system of polynomial equations has a solution. In the first part of this paper, we construct new … Read more