Hi, I am Tianran Chen

I am an Associate Professor at Auburn University at Montgomery in the Department of Mathematics (Distinguished Research Associate Professor of Mathematics). I studied under the guidance of Tien-Yien Li and received my Ph.D. in Applied Mathematics from Michigan State University.

My main research interests are numerical analysis and scientific computing as well as their applications in physics, chemistry, biology, and engineering. My current research focuses on numerical algebraic geometry with applications in power flow studies and is supported by the National Science Foundation through award DMS-2318837. You can find out more about my research here. For more information, please see my CV here (PDF version).

In the Fall semester of 2024 I am teaching

MATH-1610 (Calculus I),
MATH-1620 (Calculus II)

…and manage online courses

MATH-1020 (Online)

Office hours

Office: 310A Goodwyn Hall
Office hour:
- Mon, Wed, Tue, Thu: 3:15pm – 4:30pm
- …and by appointment

Hiring

I am always hiring student research assistants. See detail here.

Grants

2024-2027 NSF research grant DMS-2318837 AMPS: Topological disturbance for power flow equations through the lens of convex and algebraic geometry $149,940 Role: PI (with a subaward for University of Texas at Austin managed by co-PIs Julia Lindberg and Joseph Kileel)
2023–2025 AMS-Simons Research Enhancement Grant for Primarily Undergraduate Institution Faculty
2019–2023 NSF research grant DMS-1923099 AMPS: Collaborative Research: A Convex Geometry and Homotopy Approach for Power-Flow Equations $105,281 Role: PI (in collaboration with separately funded co-PI Robert Davis)
2022–2024 AUM Grant-in-aid award
2020–2022 AUM Grant-in-aid award
2018–2020 AUM Grant-in-aid award
2016–2019 AMS-Simons Travel Grant

News and recent talks

Recently, I gave a talk titled Polynomials in economics and polyhedral homotopy in the workshop Invitation to Algebraic Statistics and Applications which is a part of the long program on Algebraic Statistics and Our Changing World hosted by Institute of Mathematical and Statistical Innovation at the University of Chicago
September 21, 2023
University of Chicago, Chicago, IL, USA.
[ talk slides ]
I gave a talk titled Stratified polyhedral homotopy in the AMS Special Session on Polynomial Systems, Homotopy Continuation and Applications during the Joint Mathematics Meetings
January 4, 2023
Boston, MA, USA.
[ talk slides ]

Scientific Software

libtropicon A library for computing intersection points of generic tropical hypersurfaces.
Hom4PS-3: A parallel numerical solver for systems of polynomial equations based on the Polyhedral Homotopy Method.
MixedVol-3: A parallel software package for computing mixed volume, BKK bound, and fine mixed subdivisions (now a part of Hom4PS-3).
libtropicana: A library designed to find regular simplicial subdivision of lattice convex polytopes and also compute normalized volume as a byproduct. It is written completely in C++ with optional interface for leveraging spBLAS (Sparse BLAS) routines. It is open source software. Users may freely distribute its source under the terms of the LGPLv3 license.

Preprints

"A stratified polyhedral homotopy method for sampling positive dimensional zero sets of polynomial systems"
[ pdf ] [ arXiv ] [ abstract ] [ bibtex ]

Abstract: Numerical algebraic geometry revolves around the study of solutions to polynomial systems via numerical method. The polyhedral homotopy of Huber and Sturmfels for computing isolated solutions and the concept of witness sets as numerical representations of non-isolated solution components, put forth by Sommese and Wampler, are two of the fundamental tools in this field. In this paper, we show that a modified polyhedral homotopy can reveal sample sets of non-isolated solution components, akin to witness sets, as by-products from the process of computing isolated solutions. In certain cases, this method also leads to a natural decomposition of the BKK bound into a sum of local contributions from individual irreducible components.
```
@article{Chen2023Stratified, 
  year = {2023}, 
  title = {{A stratified polyhedral homotopy method for sampling positive dimensional zero sets of polynomial systems}}, 
  author = {Chen, Tianran}, 
  journal = {arXiv}, 
  eprint = {2304.08598}
}
```
(with Daniel Bates, Paul Breiding, Jonathan Hauenstein, Anton Leykin, and Frank Sottile)
"Numerical Nonlinear Algebra"
[ pdf ] [ arXiv ] [ abstract ] [ bibtex ]

Abstract: Numerical nonlinear algebra is a computational paradigm that uses numerical analysis to study polynomial equations. Its origins were methods to solve systems of polynomial equations based on the classical theorem of Bézout. This was decisively linked to modern developments in algebraic geometry by the polyhedral homotopy algorithm of Huber and Sturmfels, which exploited the combinatorial structure of the equations and led to efficient software for solving polynomial equations. Subsequent growth of numerical nonlinear algebra continues to be informed by algebraic geometry and its applications. These include new approaches to solving, algorithms for studying positive-dimensional varieties, certification, and a range of applications both within mathematics and from other disciplines. With new implementations, numerical nonlinear algebra is now a fundamental computational tool for algebraic geometry and its applications.
```
@article{Bates2023Numerical, 
  year = {2023}, 
  title = {{Numerical Nonlinear Algebra}}, 
  author = {Bates, Daniel J and Breiding, Paul and Chen, Tianran and Hauenstein, Jonathan D and Leykin, Anton and Sottile, Frank}, 
  journal = {arXiv}, 
  eprint = {2302.08585}
}
```
(with Evgeniia Korchevskaia and Julia Lindberg)
"On the typical and atypical solutions to the Kuramoto equations"
[ pdf ] [ arXiv ] [ abstract ] [ bibtex ]

Abstract: The Kuramoto model is a dynamical system that models the interaction of coupled oscillators. There has been much work to effectively bound the number of equilibria to the Kuramoto model for a given network. By formulating the Kuramoto equations as a system of algebraic equations, we first relate the complex root count of the Kuramoto equations to the combinatorics of the underlying network by showing that the complex root count is generically equal to the normalized volume of the corresponding adjacency polytope of the network. We then give explicit algebraic conditions under which this bound is strict and show that there are conditions where the Kuramoto equations have infinitely many equilibria.
```
@article{Chen2022Typical,
  archivePrefix = {arXiv},
  arxivId = {2210.00784},
  author = {Chen, Tianran and Korchevskaia, Evgeniia and Lindberg, Julia},
  eprint = {2210.00784},
  month = {oct},
  title = {On the typical and atypical solutions to the Kuramoto equations},
  url = {https://arxiv.org/abs/2210.00784},
  year = {2022}
}
```
"GPU-accelerated path tracker for polyhedral homotopy"
[ arXiv ] [ abstract ] [ bibtex ]

Abstract: The polyhedral homotopy method of Huber and Sturmfels is a particularly efficient and robust numerical method for solving system of (Laurent) polynomial equations. A central component in an implementation of this method is an efficient and scalable path tracker. While the implementation issues in a scalable path tracker for computer clusters or multi-core CPUs have been solved thoroughly, designing good GPU-based implementations is still an active research topic. This paper addresses the core issue of efficiently evaluate a multivariate system of Laurent polynomials together with all its partial derivatives. We propose a simple approach that maps particularly well onto the parallel computing architectures of modern GPUs. As a by-product, we also simplify and accelerate the path tracker by consolidating the computation of Euler and Newton directions.
```
@article{Chen2021GPU, 
  year = {2021}, 
  title = {{GPU-accelerated path tracker for polyhedral homotopy}}, 
  author = {Chen, Tianran}, 
  journal = {arXiv}, 
  doi = {10.48550/arxiv.2111.14317}, 
  eprint = {2111.14317}, 
}
```
(with Evgeniia Korchevskaia)
"On the root count of algebraic Kuramoto equations in cycle networks with uniform coupling"
[ pdf ] [ arXiv ] [ abstract ] [ bibtex ]

Abstract: The Kuramoto model is a classical model used in the study of spontaneous synchronizations in networks of coupled oscillators. In this model, frequency synchronization configurations can be formulated as complex solutions to a system of algebraic equations. Recently, upper bounds to the number of frequency synchronization configurations in cycle networks of N oscillators were calculated under the assumption of generic non-uniform coupling. In this paper, we refine these results for the special cases of uniform coupling. In particular, we show that when, and only when, N is divisible by 4, the upper bound for the number of synchronization configurations in the uniform coupling cases is significantly less than the bound in the non-uniform coupling cases. This result also establishes an explicit formula for the gap between the birationally invariant intersection index and the Bernshtein-Kushnirenko-Khovanskii bound for the underlying algebraic equations.
```
@article{ChenKorchevskaia2019Root,
  archivePrefix = {arXiv},
  arxivId = {1912.06241},
  author = {Chen, Tianran and Korchevskaia, Evgeniia},
  eprint = {1912.06241},
  month = {dec},
  title = {{On the root count of algebraic Kuramoto equations in cycle networks with uniform coupling}},
  url = {http://arxiv.org/abs/1912.06241},
  year = {2019}
}
```
(with Evgeniia Korchevskaia)
"Graph edge contraction and adjacency polytopes"
[ pdf ] [ arXiv ] [ abstract ] [ bibtex ]

Abstract: Adjacency polytopes, a.k.a. symmetric edge polytopes, associated with undirected graphs have been proposed and studied in several seemingly independent areas ranging from number theory to discrete geometry and the study of Kuramoto models. Regular subdivisions of adjacency polytopes are of particular importance in solving certain algebraic systems of equations. This paper explores the connection between the regular subdivisions of an adjacency polytope and the contraction of the underlying graph along an edge. The main result is the construction of a special regular subdivision whose cells are in one-to-one correspondence with facets of adjacency polytope associated with an edge-contraction of the original graph.
```
@article{ChenKorchevskaia2019Graph,
  archivePrefix = {arXiv},
  arxivId = {1912.02841},
  author = {Chen, Tianran and Korchevskaia, Evgeniia},
  eprint = {1912.02841},
  month = {dec},
  title = {{Graph edge contraction and adjacency polytopes}},
  url = {http://arxiv.org/abs/1912.02841},
  year = {2019}
}
```
"A geometric criterion on the equality between BKK bound and intersection"
[ pdf ] [ arXiv ] [ abstract ] [ bibtex ]

Abstract: The Bernshtein-Kushnirenko-Khovanskii theorem provides a generic root count for system of Laurent polynomials in terms of the mixed volume of their Newton polytopes (i.e., the BKK bound). A recent and far-reaching generalization of this theorem is the study of birationally invariant intersection index by Kaveh and Khovanskii. This short note establishes a simple geometric condition on the equality between the BKK bound and the intersection index for a system of vector spaces of Laurent polynomials. Applying this, we show that the intersection index for the algebraic Kuramoto equations equals their BKK bound.
```
@article{Chen2023Geometric,
  archivePrefix = {arXiv},
  arxivId = {1812.05408},
  author = {Chen, Tianran},
  eprint = {1812.05408},
  month = {apr},
  title = {{A geometric criterion on the equality between BKK bound and intersection}},
  url = {http://arxiv.org/abs/1812.05408},
  year = {2023}
}
```
(with Dhagash Mehta)
"An index-resolved fixed-point homotopy and potential energy landscapes"
[ arXiv ] [ abstract ] [ bibtex ]

Abstract: Stationary points (SPs) of the potential energy landscapes can be classified by their Morse index, i.e., the number of negative eigenvalues of the Hessian evaluated at the SPs. In understanding chemical clusters through their potential energy landscapes, only SPs of a particular Morse index are needed. We propose a modification of the "fixed-point homotopy" method which can be used to directly target stationary points of a specified Morse index. We demonstrate the effectiveness of our approach by applying it to the Lennard-Jones clusters.
```
@article{chen_index_2015,
annote = {Comment: 7 pages, 2 figures},
author = {Chen, Tianran and Mehta, Dhagash},
journal = {arXiv:1504.06622 [cond-mat]},
month = {apr},
title = {An index-resolved fixed-point homotopy and potential energy landscapes},
url = {http://arxiv.org/abs/1504.06622},
year = {2015}
}
```

Publications

"Volume of convex polytopes equals mixed volume of simplices"
Archiv der Mathematik (2023)
[ link ] [ pdf ] [ arXiv ] [ abstract ] [ bibtex ]

Abstract: We provide a simple proof for the equality between the normalized volume of a convex polytope with $m$ vertices and the mixed volume of $m$ simplices and thus show the seemingly restrictive problem of computing mixed volume of simplices is still at least as hard as computing volumes of convex polytopes in general.
```
@article{Chen2023Volume, 
  year = {2023}, 
  title = {{Volume of convex polytopes equals mixed volume of simplices}}, 
  author = {Chen, Tianran}, 
  journal = {Archiv der Mathematik}, 
  issn = {0003-889X}, 
  doi = {10.1007/s00013-023-01836-3}, 
  pages = {1--6}, 
  keywords = {}
}
```
(with Robert Davis and Evgeniia Korchevskaia)
"Facets and facet subgraphs of symmetric edge polytopes"
Discrete Applied Mathematics (2022)
[ link ] [ pdf ] [ arXiv ] [ abstract ] [ bibtex ]

Abstract: Symmetric edge polytopes, a.k.a. PV-type adjacency polytopes, associated with undirected graphs have been defined and studied in several seemingly independent areas including number theory, discrete geometry, and dynamical systems. In particular, the authors are motivated by the study of the algebraic Kuramoto equations of unmixed form whose Newton polytopes are the symmetric edge polytopes. The interplay between the geometric structure of symmetric edge polytopes and the topological structure of the underlying graphs has been a recurring theme in recent studies. In particular, "facet/face subgraphs" have emerged as one of the central concepts in describing this symmetry. Continuing along this line of inquiry we provide a complete description of the correspondence between facets/faces of a symmetric edge polytope and maximal bipartite subgraphs of the underlying connected graph.
```
@article{ChenDavisKorchevskaia2022Facets,
  title = {Facets and facet subgraphs of symmetric edge polytopes},
  journal = {Discrete Applied Mathematics},
  volume = {328},
  pages = {139-153},
  year = {2023},
  issn = {0166-218X},
  doi = {https://doi.org/10.1016/j.dam.2022.11.015},
  url = {https://www.sciencedirect.com/science/article/pii/S0166218X22004462},
  author = {Tianran Chen and Robert Davis and Evgeniia Korchevskaia},
  keywords = {Symmetric edge polytope, Adjacency polytope, Kuramoto equations},
}
```
(with Robert Davis)
"A toric deformation method for solving Kuramoto equations on cycle networks"
Nonlinear Dynamics (2022)
[ link ] [ pdf ] [ arXiv ] [ abstract ] [ bibtex ]

Abstract: The study of frequency synchronization configurations in Kuramoto models is a ubiquitous mathematical problem that has found applications in many seemingly independent fields. In this paper, we focus on networks whose underlying graph are cycle graphs. Based on the recent result on the upper bound of the frequency synchronization configurations in this context, we propose a toric deformation homotopy method for locating all frequency synchronization configurations with complexity that is linear in this upper bound. Loosely based on the polyhedral homotopy method, this homotopy induces a deformation of the set of the synchronization configurations into a series of toric varieties, yet our method has the distinct advantage of avoiding the costly step of computing mixed cells. We also explore the important consequences of this homotopy method in the context of direct acyclic decomposition of Kuramoto networks and tropical stable intersection points for Kuramoto equations.
```
@article{ChenDavis2022Toric,
  author = {Tianran Chen and Robert Davis},
  doi = {10.1007/s11071-022-07550-z},
  issn = {1573269X},
  journal = {Nonlinear Dynamics},
  keywords = {Adjacency polytope,Kuramoto model,Polyhedral homotopy,Tropical geometry},
  month = {6},
  pages = {1-20},
  publisher = {Springer Science and Business Media B.V.},
  title = {A toric deformation method for solving Kuramoto equations on cycle networks},
  url = {https://link.springer.com/article/10.1007/s11071-022-07550-z},
  year = {2022},
}
```
(with Robert Davis, (I made minor contributions))
"Computing volumes of adjacency polytopes via draconian sequences"
Electronic Journal of Combinatorics (2022)
[ link ] [ pdf ] [ arXiv ] [ abstract ] [ bibtex ]

Abstract: Adjacency polytopes of graphs appear naturally in the study of nonlinear emergent phenomenon in complex networks. The "type-PV" adjacency polytope, also known as a symmetric edge polytope, arises in the study of Kuramoto equations. The "type-PQ" adjacency polytope of the graph G, denote by $\nabla^{PQ}_G$, which is the focus of this work, encodes rich combinatorial information about power-flow solutions in sparse power networks that are studied in electric engineering. Of particular importance is the normalized volume of such an adjacency polytope, which provides an upper bound on the number of distinct power-flow solutions. In this article we show that the problem of computing normalized volumes for the type-PQ adjacency polytopes can be rephrased as the problem of counting $D(G)$-draconian sequences where $D(G)$ is a certain bipartite graph associated to the network. We provide recurrences for all networks with connectivity as most 1 and, for 2-connected graphs, we give, under an additional mild restriction, recurrences for subdividing an edge and taking the join of an edge with a new vertex. Together, these recurrences imply a simple, non-recursive formula for the normalized volume of $\nabla^{PQ}_G$ when $G$ is part of a large class of outerplanar graphs; we conjecture that the formula holds for all outerplanar graphs. Explicit formulas for several other (non-outerplanar) classes are given. Further, we identify several important classes of graphs G which are planar but not outerplanar worth additional study.
```
@article{DavisChen2022Computing,
  author = {Robert Davis and Tianran Chen},
  doi = {10.37236/9768},
  issn = {1077-8926},
  issue = {1},
  journal = {The Electronic Journal of Combinatorics},
  month = {3},
  pages = {P1.61-P1.61},
  title = {Computing Volumes of Adjacency Polytopes via Draconian Sequences},
  volume = {29},
  url = {https://www.combinatorics.org/ojs/index.php/eljc/article/view/v29i1p61},
  year = {2022},
}
```
(with Dhagash Mehta, Tingting Tang and Jonathan D. Hauenstein)
"The loss surface of deep linear networks viewed through the algebraic geometry lens"
IEEE Transactions on Pattern Analysis and Machine Intelligence (2021)
[ link ] [ pdf ] [ arXiv ] [ abstract ] [ bibtex ]

Abstract: By using the viewpoint of modern computational algebraic geometry, we explore properties of the optimization landscapes of the deep linear neural network models. After clarifying on the various definitions of "flat" minima, we show that the geometrically flat minima, which are merely artifacts of residual continuous symmetries of the deep linear networks, can be straightforwardly removed by a generalized $L_2$ regularization. Then, we establish upper bounds on the number of isolated stationary points of these networks with the help of algebraic geometry. Using these upper bounds and utilizing a numerical algebraic geometry method, we find all stationary points for modest depth and matrix size. We show that in the presence of the non-zero regularization, deep linear networks indeed possess local minima which are not the global minima. Our computational results further clarify certain aspects of the loss surfaces of deep linear networks and provides novel insights.
```
@article{MehtaChenTangHauenstein2021,
archivePrefix = {arXiv},
arxivId = {1810.07716},
doi = {10.1109/TPAMI.2021.3071289},
journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence},
author = {Mehta, Dhagash and Chen, Tianran and Tang, Tingting and Hauenstein, Jonathan D.},
eprint = {1810.07716},
month = {oct},
title = {The loss surface of deep linear networks viewed through the algebraic geometry lens},
url = {http://arxiv.org/abs/1810.07716},
year = {2021}
}
```
(with Jakub Mareček, Dhagash Mehta, and Matthew Niemerg)
"Three formulations of the Kuramoto model as a system of polynomial equations"
2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton), Monticello, IL, USA, 2019, pp. 810-815
[ link ] [ arXiv ] [ abstract ] [ bibtex ]

Abstract: We compare three formulations of stationary equations of the Kuramoto model as systems of polynomial equations. In the comparison, we present bounds on the numbers of real equilibria based on the work of Bernstein, Kushnirenko, and Khovanskii, and performance of methods for the optimisation over the set of equilibria based on the work of Lasserre, both of which could be of independent interest.
```
@INPROCEEDINGS{ChenMarecekMehtaNiemerg2019Three,
  author={Chen, Tianran and Mareček, Jakub and Mehta, Dhagash and Niemerg, Matthew},
  booktitle={2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton)}, 
  title={Three Formulations of the Kuramoto Model as a System of Polynomial Equations}, 
  year={2019},
  volume={},
  number={},
  pages={810-815},}
```
"Directed acyclic decomposition of Kuramoto equations"
Chaos: An Interdisciplinary Journal of Nonlinear Science, Vol.29, Issue 9 2019
[ link ] [ pdf ] [ arXiv ] [ abstract ] [ bibtex ]

Abstract: The Kuramoto model is one of the most widely studied model for describing synchronization behaviors in a network of coupled oscillators, and it has found a wide range of applications. Finding all possible frequency synchronization configurations in a general non-uniform heterogeneous sparse network is an important yet difficult problem due to the complicated nonlinear interactions. In this paper, we develop a general framework for decomposing a Kuramoto network into smaller directed acyclic subnetworks that will form the foundation of a divide-and-conquer approach for studying the frequency synchronization configurations of large Kuramoto networks.
```
@article{Chen2019Directed,
  author = {Chen, Tianran},
  doi = {10.1063/1.5097826},
  issn = {1054-1500},
  journal = {Chaos: An Interdisciplinary Journal of Nonlinear Science},
  month = {Sep},
  number = {9},
  pages = {093101},
  publisher = {AIP Publishing LLC},
  title = {{Directed acyclic decomposition of Kuramoto equations}},
  url = {http://aip.scitation.org/doi/10.1063/1.5097826},
  volume = {29},
  year = {2019}
}
```
"Unmixing the mixed volume computation"
Discrete & Computational Geometry (2019) 62:55–86
[ link ] [ pdf ] [ arXiv ] [ abstract ] [ bibtex ]

Abstract: Computing mixed volume of convex polytopes is an important problem in computational algebraic geometry. This paper establishes sufficient conditions under which the mixed volume of several convex polytopes exactly equals the normalized volume of the convex hull of their union. Under these conditions the problem of computing mixed volume of several polytopes can be transformed into a volume computation problem for a single polytope in the same dimension. We demonstrate through problems from real world applications that substantial reduction in computational costs can be achieved via this transformation in situations where the convex hull of the union of the polytopes has less complex geometry than the original polytopes. We also discuss the important implications of this result in the polyhedral homotopy method for solving polynomial systems.
```
@article{Chen2019Unmixing,
  author="Chen, Tianran",
  title="Unmixing the Mixed Volume Computation",
  journal="Discrete {\&} Computational Geometry",
  year="2019",
  month="Mar",
  day="20",
  issn="1432-0444",
  doi="10.1007/s00454-019-00078-x",
  url="https://doi.org/10.1007/s00454-019-00078-x"
}
```
(with Robert Davis and Dhagash Mehta)
"Counting equilibria of the Kuramoto model using birationally invariant intersection index"
SIAM Journal on Applied Algebra and Geometry, 2018, Vol. 2, No. 4 pp. 489-507
[ link ] [ pdf ] [ arXiv ] [ abstract ] [ bibtex ]

Abstract: Synchronization in networks of interconnected oscillators is a fascinating phenomenon that appear naturally in many independent fields of science and engineering. A substantial amount of work has been devoted to understanding all possible synchronization configurations on a given network. In this setting, a key problem is to determine the total number of such configurations. Through an algebraic formulation, for tree and cycle graphs, we provide an upper bound on this number using the birationally invariant intersection index of a system of rational functions on a toric variety.
```
@article{ChenDavisMehta2017,
  author = {Chen, Tianran and Davis, Robert and Mehta, Dhagash},
  doi = {10.1137/17M1145665},
  issn = {2470-6566},
  journal = {SIAM Journal on Applied Algebra and Geometry},
  month = {jan},
  number = {4},
  pages = {489--507},
  title = {{Counting equilibria of the Kuramoto model using birationally invariant intersection index}},
  url = {https://epubs.siam.org/doi/10.1137/17M1145665},
  volume = {2},
  year = {2018}
}
```
"libtropicon: A Scalable Library for Computing Intersection Points of Generic Tropical Hyper-surfaces"
Mathematical Software -- ICMS 2018
[ link ] [ abstract ] [ bibtex ]

Abstract: The computation of intersection points of generic tropical hyper-surfaces is a fundamental problem in computational algebraic geometry. An efficient algorithm for solving this problem will be a basic building block in many higher level algorithms for studying tropical varieties, computing mixed volume, enumerating mixed cells, constructing polyhedral homotopies, etc. libtropicon is a library for computing intersection points of generic tropical hyper-surfaces that provides a unified framework where the several conceptually opposite approaches coexist and complement one another. In particular, great efficiency is achieve by the data cross-feeding of the ``pivoting'' and the ``elimination'' step --- data by-product generated by the pivoting step is selectively saved to bootstrap the elimination step, and vice versa. The core algorithm is designed to be naturally parallel and highly scalable, and the implementation directly supports multi-core architectures, computer clusters, and GPUs based on CUDA or ROCm/OpenCL technology. Many-core architectures such as Intel Xeon Phi are also partially supported. This library also includes interface layers that allows it to be tightly integrated into the existing ecosystem of software in computational algebraic geometry.
```
@InProceedings{Chen2018Libtropicon
  author="Chen, Tianran",
  editor="Davenport, James H. and Kauers, Manuel and Labahn, George and Urban, Josef",
  title="libtropicon: A Scalable Library for Computing Intersection Points of Generic Tropical Hyper-surfaces",
  booktitle="Mathematical Software -- ICMS 2018",
  year="2018",
  publisher="Springer International Publishing",
  address="Cham",
  pages="105--112",
  isbn="978-3-319-96418-8"
}
```
(with Robert Davis)
"A Product Formula for the Normalized Volume of Free Sums of Lattice Polytopes"
Advances in Algebra: Research from the Southern Regional Algebra Conference 2017
[ link ] [ arXiv ] [ abstract ] [ bibtex ]

Abstract: The free sum is a basic geometric operation among convex polytopes. This note focuses on the relationship between the normalized volume of the free sum and that of the summands. In particular, we show that the normalized volume of the free sum of full dimensional polytopes is precisely the product of the normalized volumes of the summands.
```
@InProceedings{ChenDavis2019Product,
  author="Chen, Tianran and Davis, Robert",
  editor="Feldvoss, J{\"o}rg and Grimley, Lauren and Lewis, Drew and Pavelescu, Andrei and Pillen, Cornelius",
  title="A Product Formula for the Normalized Volume of Free Sums of Lattice Polytopes",
  booktitle="Advances in Algebra",
  year="2019",
  publisher="Springer International Publishing",
  address="Cham",
  pages="111--119",
  isbn="978-3-030-11521-0"
}
```
(with Christian Knoll, Dhagash Mehta, and Franz Pernkopf)
"Fixed points of belief propagation -- An analysis via polynomial homotopy continuation"
IEEE Transactions on Pattern Analysis and Machine Intelligence
[ link ] [ pdf ] [ arXiv ] [ abstract ] [ bibtex ]

Abstract: Belief propagation (BP) is an iterative method to perform approximate inference on arbitrary graphical models. Whether BP converges and if the solution is a unique fixed point depends on both the structure and the parametrization of the model. To understand this dependence it is interesting to find all fixed points.
```
@article{knoll_fixed_2017,
author = {Knoll, Christian and Mehta, Dhagash and Chen, Tianran and Pernkopf, Franz},
doi = {10.1109/TPAMI.2017.2749575},
issn = {0162-8828},
journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence},
pages = {1--1},
title = {{Fixed Points of Belief Propagation - An Analysis via Polynomial Homotopy Continuation}},
url = {http://ieeexplore.ieee.org/document/8027142/},
year = {2017}
}
```
(with Dhagash Mehta)
"On the Network Topology Dependent Solution Count of the Algebraic Load Flow Equations"
IEEE Transactions on Power Systems (2018)
[ link ] [ pdf ] [ abstract ] [ bibtex ]

Abstract: Active research activity in power systems areas has focused on developing computational methods to solve load flow equations where a key question is the maximum number of solutions. Though several upper bounds exist, recent studies have hinted that much sharper upper bounds that depend the topology of underlying power networks may exist. This paper provides a significant refinement of these observations. We also develop a geometric construction called adjacency polytope which accurately captures the topology of a power network and is immensely useful in the computation of the solution bound. Finally we highlight the significant implications of the development of such solution bounds in numerically solving load flow equations.
```
@article{chen_network_2017,
author = {Chen, Tianran and Mehta, Dhagash},
doi = {10.1109/TPWRS.2017.2724030},
archivePrefix = {arXiv},
arxivId = {1512.04987},
eprint = {1512.04987},
issn = {08858950},
journal = {IEEE Transactions on Power Systems},
keywords = {Power systems,load flow,power system analysis computing,power system control},
title = {On the Network Topology Dependent Solution Count of the Algebraic Load Flow Equations},
url = {http://ieeexplore.ieee.org/document/7971956/},
number = {2},
pages = {1451--1460},
volume = {33},
year = {2018}
}
```
(with Tsung-Lin Lee and Tien-Yien Li)
"Mixed cell computation in Hom4PS-3"
Journal of Symbolic Computation (2017), pp. 516-534
[ link ] [ pdf ] [ abstract ] [ bibtex ]

Abstract: This article presents recent efforts in improving the efficiency and scalability of the mixed cell computation step in the context of the Polyhedral Homotopy method. Solving systems of polynomial equations is an important problem in applied mathematics. The Polyhedral Homotopy method is an important numerical method for this task. In this method, a necessary preprocessing step, known as the "mixed cell computation" problem has been the main bottleneck in the parallel efficiency and scalability. This article presents recent remarkable improvements in the parallel scalability of the algorithm that are applicable to a wide range of hardware architectures including multi-core systems, NUMA systems, computer clusters, and GPUs devices.
```
@article{chen_mixed_2017,
author = {Chen, Tianran and Lee, Tsung-Lin and Li, Tien-Yien},
doi = {10.1016/j.jsc.2016.07.017},
issn = {0747-7171},
journal = {Journal of Symbolic Computation},
month = {mar},
pages = {516--534},
series = {SI: Numerical Algebraic Geometry},
title = {{Mixed cell computation in Hom4PS-3}},
url = {http://www.sciencedirect.com/science/article/pii/S0747717116300542},
volume = {79, Part 3},
year = {2017}
}
```
(with Dhagash Mehta)
"Parallel degree computation for binomial systems"
Journal of Symbolic Computation (2017)
[ link ] [ pdf ] [ abstract ] [ bibtex ]

Abstract: Solution sets of systems of binomial equations are of great interest in applied mathematics. For both theoretic and applied purposes, the degree of a solution set (its maximum number of isolated intersections with an affine space of complementary dimension) often plays an important role in understanding its geometric structure. This paper proposes a specialized parallel algorithm for computing the degree on GPUs that takes advantage of the massively parallel nature of GPU devices. The preliminary implementation shows remarkable efficiency and scalability when compared to the closest CPU-based counterpart. As a case study, the algorithm is applied to the master space problem of N = 1 gauge theories. The GPU-based implementation achieves nearly 30 fold speedup over its CPU-only counterpart enabling the discovery of previously unknown results.
```
@article{chen_parallel_2017,
author = {Chen, Tianran and Mehta, Dhagash},
doi = {10.1016/j.jsc.2016.07.018},
issn = {0747-7171},
journal = {Journal of Symbolic Computation},
keywords = {Algebraic Geometry,BKK root-count,Binomial systems,Folder - Unmixing,GPU computing,Supersymmetric gauge theories,homotopy continuation},
month = {mar},
pages = {535--558},
series = {SI: Numerical Algebraic Geometry},
title = {{Parallel degree computation for binomial systems}},
url = {http://www.sciencedirect.com/science/article/pii/S0747717116300554},
volume = {79, Part 3},
year = {2017}
}
```

(with Dhagash Mehta, John Morgan, and David Wales)
"Response to "Comment on 'Exploring the potential energy landscape of the Thomson problem via Newton homotopies'""
The Journal of Chemical Physics 143, 247102
[ link ] [ abstract ] [ bibtex ]

Abstract: The comment notes that the Newton homotopy (NH) and Newton trajectory (NT) methods are related. By describing recent implementations of the NH method, we clarify the similarities and differences between the two approaches. The possible synergy between NH, NT and other flow methods could suggest further developments in mathematics and chemistry.

@article{mehta_response_2015,
author = {Mehta, Dhagash and Chen, Tianran and Morgan, John W. R. and Wales, David J.},
doi = {10.1063/1.4939011},
issn = {0021-9606, 1089-7690},
journal = {The Journal of Chemical Physics},
keywords = {Bifurcations,Difference equations,Flow instabilities,Flow simulations,Folder - LogEval,Folder - Unmixing,Singularity theory},
month = {dec},
number = {24},
pages = {247102},
title = {{Response to “Comment on ‘Exploring the potential energy landscape of the Thomson problem via Newton homotopies”' [J. Chem. Phys. 143, 247101 (2015)]}},
url = {http://scitation.aip.org/content/aip/journal/jcp/143/24/10.1063/1.4939011 http://scitation.aip.org/deliver/fulltext/aip/journal/jcp/143/24/1.4939011.pdf;jsessionid=23ev3700uj07.x-aip-live-03?itemId=/content/aip/journal/jcp/143/24/10.1063/1.4939011{\&}mimeTyp},
volume = {143},
year = {2015}
}

(with Tien-Yien Li)
"Homotopy continuation method for solving systems of nonlinear and polynomial equations"
Communications in Information and Systems 15(2):119--307 (2015)
[ link ] [ abstract ] [ bibtex ]

Abstract: This survey provides an overview of the homotopy continuation method for solving systems of nonlinear and polynomial equations including its theoretical background, numerical stability analysis, and implementation issues.
```
@article{chen_homotopy_2015,
author = {Chen, Tianran and Li, Tien-Yien},
doi = {10.4310/CIS.2015.v15.n2.a1},
issn = {15267555, 21634548},
journal = {Commun. Inf. Syst.},
number = {2},
pages = {119--307},
title = {Homotopy continuation method for solving systems of nonlinear and polynomial equations},
volume = {15},
year = {2015}
}
```
(with Dhagash Mehta, John Morgan, and David Wales)
"Exploring the potential energy landscape of the Thomson problem via Newton homotopies"
The Journal of Chemical Physics 142 194113 (2015)
[ link ] [ pdf ] [ abstract ] [ bibtex ]

Abstract: Locating the stationary points of a real-valued multivariate potential energy function is an important problem in many areas of science. This task generally amounts to solving simultaneous nonlinear systems of equations. While there are several numerical methods that can find many or all stationary points, they each exhibit characteristic problems. Moreover, traditional methods tend to perform poorly near degenerate stationary points with additional zero Hessian eigenvalues. We propose an efficient and robust implementation of the Newton homotopy method, which is capable of quickly sampling a large number of stationary points of a wide range of indices, as well as degenerate stationary points. We demonstrate our approach by applying it to the Thomson problem. We also briefly discuss a possible connection between the present work and Smale's 7th problem.
```
@article{mehta_exploring_2015,
author = {Mehta, Dhagash and Chen, Tianran and Morgan, John W. R. and Wales, David J.},
doi = {10.1063/1.4921163},
issn = {0021-9606, 1089-7690},
journal = {The Journal of Chemical Physics},
keywords = {Eigenvalues,Folder - Finished - NewtonHomotopyReply,Folder - Finished - Solving survey,Folder - LogEval,Folder - Power flow,Folder - Unmixing,Newton Raphson method,Nonlinear dynamics,Numerical solutions,Potential energy surfaces},
month = {may},
number = {19},
pages = {194113},
title = {{Exploring the potential energy landscape of the Thomson problem via Newton homotopies}},
url = {http://scitation.aip.org/content/aip/journal/jcp/142/19/10.1063/1.4921163},
volume = {142},
year = {2015}
}
```
(with Tien-Yien Li and Xiaoshen Wang)
"Theoretical aspects of mixed volume computation via mixed subdivision"
Communications in Information and Systems (2014)
[ link ] [ pdf ] [ abstract ] [ bibtex ]

Abstract: We analyze the computation of mixed volume of tuples of polytopes via fine mixed subdivisions. This method expresses the mixed volume as a sum of easily computable standard volumes of polytopes called mixed cells. Mixed cells play a critically important role in polyhedral homotopy continuation method, which in turn is a particularly efficient numerical method for the solution of systems of polynomial equations. We provide a complete and self-contained account of the underlying computational convexity techniques, assuming no background in algebraic geometry.
```
@article{chen_theoretical_2014,
author = {Chen, Tianran and Li, Tien-Yien and Wang, Xiaoshen},
doi = {10.4310/CIS.2014.v14.n4.a1},
issn = {15267555, 21634548},
journal = {Communications in Information and Systems},
number = {4},
pages = {213--242},
title = {Theoretical aspects of mixed volume computation via mixed subdivision},
url = {http://www.intlpress.com/site/pub/pages/journals/items/cis/content/vols/0014/0004/a001/},
volume = {14},
year = {2014}
}
```
(with Dhagash Mehta, Jonathan Hauenstein, and David Wales)
"Newton homotopies for sampling stationary points of potential energy landscapes"
The Journal of Chemical Physics 141 (12), 121104 (2014)
[ link ] [ pdf ] [ arXiv ] [ abstract ] [ bibtex ]

Abstract: One of the most challenging and frequently arising problems in many areas of science is to find solutions of a system of multivariate nonlinear equations. There are several numerical methods that can find many (or all if the system is small enough) solutions but they all exhibit characteristic problems. Moreover, traditional methods can break down if the system contains singular solutions. Here, we propose an efficient implementation of Newton homotopies, which can sample a large number of the stationary points of complicated many-body potentials. We demonstrate how the procedure works by applying it to the nearest-neighbor ϕ4 model and atomic clusters.
```
@article{mehta_newton_2014,
author = {Mehta, Dhagash and Chen, Tianran and Hauenstein, Jonathan D and Wales, David J},
doi = {10.1063/1.4896657},
issn = {0021-9606, 1089-7690},
journal = {The Journal of Chemical Physics},
keywords = {Atomic and molecular clusters,Biomolecular structure,Nonlinear differential equations,Numerical modeling,Numerical solutions,real homotopy},
month = {sep},
number = {12},
pages = {121104},
shorttitle = {Communication},
title = {Newton homotopies for sampling stationary points of potential energy landscapes},
url = {http://scitation.aip.org/content/aip/journal/jcp/141/12/10.1063/1.4896657},
volume = {141},
year = {2014}
}
```
(with Tien-Yien Li)
"Solutions to systems of binomial equations"
Annales Mathematicae Silesianae 28:7–34 (2014)
[ link ] [ pdf ] [ abstract ] [ bibtex ]

Abstract: This paper provides an overview on the geometry of solutions to binomial equations (equations that have exactly two terms) as well as the numerical methods for solving such systems.
```
@article{chen_solutions_2014,
author = {Chen, Tianran and Li, Tien-Yien},
journal = {Annales Mathematicae Silesianae},
pages = {7--34},
title = {{Solutions to systems of binomial equations}},
volume = {28},
year = {2014}
}
```
(with Tsung-Lin Lee, and Tien-Yien Li)
"Hom4PS-3: A Parallel Numerical Solver for Systems of Polynomial Equations Based on Polyhedral Homotopy Continuation Methods (extended abstract)"
Mathematical Software -- ICMS 2014 -- 4th International Congress, Seoul, South Korea, August 5-9, 2014. Proceedings 8592:183–190
[ link ] [ abstract ] [ bibtex ]

Abstract: Homotopy continuation methods have been proved to be an efficient and reliable class of numerical methods for solving systems of polynomial equations which occur frequently in various fields of mathematics, science, and engineering. Based on the successful software package Hom4PS-2.0 for solving such polynomial systems, Hom4PS-3 has a new fully modular design which allows it to be easily extended. It implements many different numerical homotopy methods including the Polyhedral Homotopy continuation method. Furthermore, it is capable of carrying out computation in parallel on a wide range of hardware architectures including multi-core systems, computer clusters, distributed environments, and GPUs with great efficiency and scalability. Designed to be user-friendly, it includes interfaces to a variety of existing mathematical software and programming languages such as Python, Ruby, Octave, Sage and Matlab.
```
@incollection{chen_hom4ps-3,
author = {Chen, Tianran and Lee, Tsung-Lin and Li, Tien-Yien},
booktitle = {Mathematical Software – ICMS 2014},
editor = {Hong, Hoon and Yap, Chee},
isbn = {978-3-662-44198-5 978-3-662-44199-2},
keywords = {Algorithm Analysis and Problem Complexity,Discrete Mathematics in Computer Science,Math Applications in Computer Science,Numeric Computing,Software Engineering/Programming and Operating Sy,Theory of Computation,binomial system,homotopy continuation,polyhedral homotopy,polynomial systems},
month = {jan},
number = {8592},
pages = {183--190},
publisher = {Springer Berlin Heidelberg},
series = {Lecture Notes in Computer Science},
shorttitle = {Hom4PS-3},
title = {{Hom4PS-3: A Parallel Numerical Solver for Systems of Polynomial Equations Based on Polyhedral Homotopy Continuation Methods}},
url = {http://link.springer.com/chapter/10.1007/978-3-662-44199-2{\_}30},
year = {2014}
}
```
(with Tsung-Lin Lee and Tien-Yien Li)
"Mixed volume computation in parallel"
Taiwanese Journal of Mathematics 18(1):93–114 (2014)
[ link ] [ pdf ] [ abstract ] [ bibtex ]

Abstract: Efficient algorithms for computing mixed volumes, via the computation of mixed cells, have been implemented in DEMiCs and MixedVol-2.0. While the approaches in those two packages are somewhat different, they follow the same theme and are both highly serial. To fit the need for the parallel computing, a reformulation of the algorithms is inevitable. This article proposes a reformulation of the algorithm for the mixed volume computation rooted from algorithms in graph theory, making it much more fine-grained and scalable. The resulting parallel algorithm can be readily adapted to both distributed and shared memory computing systems. Illustrated by the numerical results on several different architectures, the speedups of our parallel algorithms for the mixed volume computation are remarkable.
```
@article{chen_mixed_2014,
author = {Chen, Tianran and Lee, Tsung-Lin and Li, Tien-Yien},
journal = {Taiwanese Journal of Mathematics},
keywords = {bkk,mixed cells,mixed volume},
number = {1},
pages = {93--114},
title = {Mixed volume computation in parallel},
volume = {18},
year = {2014}
}
```
(with Tien-Yien Li)
"Spherical projective path tracking for homotopy continuation methods"
Communications in Information and Systems 12(3):195-220 (2012)
[ link ] [ pdf ] [ abstract ] [ bibtex ]

Abstract: Solving systems of polynomial equations is an important problem in mathematics with a wide range of applications in many fields. The homotopy continuation method is a large class of reliable and efficient numerical methods for solving systems of polynomial equations. An essential component in the homotopy continuation method is the path tracking algorithm for tracking smooth paths of one real dimension. In this regard, “divergent paths” pose a tough challenge as the tracking of such paths is generally impossible. The existence of such paths is, in part, caused by $\mathbb{C}^n$, the space in which homotopy methods usually operate, being non-compact. A well known remedy is to operate inside the complex projective space $\mathbb{CP}^n$ instead. Path tracking inside $\mathbb{CP}^n$ is the focus of this article. Taking the Riemannian geometry of $\mathbb{CP}^n$ into account, we derive the basic algorithm for projective path tracking using the sphere, $S^{2n+1}$, as the model of computation. Remarkable results from numerical experiments using this method are presented.
```
@article{chen_spherical_2012,
author = {Chen, Tianran and Li, Tien-Yien},
journal = {Communication in Information and Systems},
number = {3},
pages = {195--220},
title = {Spherical projective path tracking for homotopy continuation methods},
volume = {12},
year = {2012}
}
```