Consider an algorithm computing in a differential field with several commuting derivations such that the only operations it performs with the elements of the field are arithmetic operations, differentiation, and zero testing. We show that, if the algorithm is guaranteed to terminate on every input, then there is a computable upper bound for the size of the output of the algorithm in terms of the size of the input. We also generalize this to algorithms working with models of good enough theories (including, for example, difference fields).
We then apply this to differential algebraic geometry to show that there exists a computable uniform upper bound for the number of components of any variety defined by a system of polynomial PDEs. We then use this bound to show the existence of a computable uniform upper bound for the elimination problem in systems of polynomial PDEs with delays.
more »
« less
Geolocation with FDOA measurements via polynomial systems and RANSAC
The problem of geolocation of a radiofrequency
transmitter via time difference of arrival
(TDOA) and frequency difference of arrival (FDOA) is
given as a system of polynomial equations. This allows
for the use of homotopy continuation-based methods from
numerical algebraic geometry. A novel geolocation algorithm
employs numerical algebraic geometry techniques in
conjunction with the random sample consensus (RANSAC)
method. This is all developed and demonstrated in the
setting of only FDOA measurements, without loss of generality.
Additionally, the problem formulation as polynomial
systems immediately provides lower bounds on the number
of receivers or measurements required for the solution set
to consist of only isolated points.
more »
« less
- Award ID(s):
- 1719658
- NSF-PAR ID:
- 10073090
- Date Published:
- Journal Name:
- 2018 IEEE Radar Conference (RadarConf18)
- Page Range / eLocation ID:
- 0676 to 0681
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)Abstract We present a new method for the stable reconstruction of a class of binary images from a small number of measurements. The images we consider are characteristic functions of algebraic domains, that is, domains defined as zero loci of bivariate polynomials, and we assume to know only a finite set of uniform samples for each image. The solution to such a problem can be set up in terms of linear equations associated to a set of image moments. However, the sensitivity of the moments to noise makes the numerical solution highly unstable. To derive a robust image recovery algorithm, we represent algebraic polynomials and the corresponding image moments in terms of bivariate Bernstein polynomials and apply polynomial-generating, refinable sampling kernels. This approach is robust to noise, computationally fast and simple to implement. We illustrate the performance of our reconstruction algorithm from noisy samples through extensive numerical experiments. Our code is released open source and freely available.more » « less
-
Predictive modeling in physical science and engineering is mostly based on solving certain partial differential equations where the complexity of solutions is dictated by the geometry of the domain. Motivated by the broad applications of explicit solutions for spherical and ellipsoidal domains, in particular, the Eshelby’s solution in elasticity, we propose a generalization of ellipsoidal shapes called polynomial inclusions. A polynomial inclusion (or -inclusion for brevity) of degree is defined as a smooth, connected and bounded body whose Newtonian potential is a polynomial of degree inside the body. From this viewpoint, ellipsoids are identified as the only -inclusions of degree two; many fundamental problems in various physical settings admit simple closed-form solutions for general -inclusions as for ellipsoids. Therefore, we anticipate that -inclusions will be useful for applications including predictive materials models, optimal designs, and inverse problems. However, the existence of p-inclusions beyond degree two is not obvious, not to mention their explicit algebraic parameterizations. In this work, we explore alternative definitions and properties of p-inclusions in the context of potential theory. Based on the theory of variational inequalities, we show that -inclusions do exist for certain polynomials, though a complete characterization remains open. We reformulate the determination of surfaces of -inclusions as nonlocal geometric flows which are convenient for numerical simulations and studying geometric properties of -inclusions. In two dimensions, by the method of conformal mapping we find an explicit algebraic parameterization of p-inclusions. We also propose a few open problems whose solution will deepen our understanding of relations between domain geometry, Newtonian potentials, and solutions to general partial differential equations. We conclude by presenting examples of applications of -inclusions in the context of Eshelby inclusion problems and magnet designs.more » « less
-
null (Ed.)The object of study of this paper is the following multi-determinantal algebraic variety, SINGn, m, which captures the symbolic determinant identity testing (SDIT) problem (a canonical version of the polynomial identity testing (PIT) problem), and plays a central role in algebra, algebraic geometry and computational complexity theory. SINGn, m is the set of all m-tuples of n×n complex matrices which span only singular matrices. In other words, the determinant of any linear combination of the matrices in such a tuple vanishes. The algorithmic complexity of testing membership in SINGn, m is a central question in computational complexity. Having almost a trivial probabilistic algorithm, finding an efficient deterministic algorithm is a holy grail of derandomization, and to top it, will imply super-polynomial circuit lower bounds! A sequence of recent works suggests efficient deterministic “geodesic descent” algorithms for memberships in a general class of algebraic varieties, namely the null cones of (reductive) linear group actions. Can such algorithms be used for the problem above? Our main result is negative: SINGn, m is not the null cone of any such group action! This stands in stark contrast to a non-commutative analog of this variety (for which such algorithms work), and points to an inherent structural difficulty of SINGn, m. In other words, we provide a barrier for the attempts of derandomizing SDIT via these algorithms. To prove this result we identify precisely the group of symmetries of SINGn, m. We find this characterization, and the tools we introduce to prove it, of independent interest. Our characterization significantly generalizes a result of Frobenius for the special case m=1 (namely, computing the symmetries of the determinant). Our proof suggests a general method for determining the symmetries of general algebraic varieties, an algorithmic problem that was hardly studied and we believe is central to algebraic complexity.more » « less
-
In numerical linear algebra, a well-established practice is to choose a norm that exploits the structure of the problem at hand to optimise accuracy or computational complexity. In numerical polynomial algebra, a single norm (attributed to Weyl) dominates the literature. This article initiates the use of L_p norms. This classical idea yields strong improvements in the analysis of the number of steps performed by numerous iterative algorithms. In particular, we exhibit three algorithms where, despite the complexity of computing L_{infinity } norm the use L_p norms substantially reduces computational complexity: a subdivision-based algorithm in real algebraic geometry for computing the homology of semialgebraic sets, a well-known meshing algorithm in computational geometry and the computation of zeros of systems of complex quadratic polynomials (a particular case of Smale’s 17th problem).more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/RADAR.2018.8378640
