-
Mirror symmetry for tropical hypersurfaces and patchworking
Authors:
Diego Matessi,
Arthur Renaudineau
Abstract:
In the first part of the paper, we prove a mirror symmetry isomorphism between integral tropical homology groups of a pair of mirror tropical Calabi-Yau hypersurfaces. We then apply this isomorphism to prove that a primitive patchworking of a central triangulation of a reflexive polytope gives a connected real Calabi-Yau hypersurface if and only if the corresponding divisor class on the mirror is…
▽ More
In the first part of the paper, we prove a mirror symmetry isomorphism between integral tropical homology groups of a pair of mirror tropical Calabi-Yau hypersurfaces. We then apply this isomorphism to prove that a primitive patchworking of a central triangulation of a reflexive polytope gives a connected real Calabi-Yau hypersurface if and only if the corresponding divisor class on the mirror is not zero.
△ Less
Submitted 18 July, 2024;
originally announced July 2024.
-
Energy landscapes of combinatorial optimization in Ising machines
Authors:
Dmitrii Dobrynin,
Adrien Renaudineau,
Mohammad Hizzani,
Dmitri Strukov,
Masoud Mohseni,
John Paul Strachan
Abstract:
Physics-based Ising machines (IM) have been developed as dedicated processors for solving hard combinatorial optimization problems with higher speed and better energy efficiency. Generally, such systems employ local search heuristics to traverse energy landscapes in searching for optimal solutions. Here, we quantify and address some of the major challenges met by IMs by extending energy-landscape…
▽ More
Physics-based Ising machines (IM) have been developed as dedicated processors for solving hard combinatorial optimization problems with higher speed and better energy efficiency. Generally, such systems employ local search heuristics to traverse energy landscapes in searching for optimal solutions. Here, we quantify and address some of the major challenges met by IMs by extending energy-landscape geometry visualization tools known as disconnectivity graphs. Using efficient sampling methods, we visually capture landscapes of problems having diverse structure and hardness manifesting as energetic and entropic barriers for IMs. We investigate energy barriers, local minima, and configuration space clustering effects caused by locality reduction methods when embedding combinatorial problems to the Ising hardware. To this end, we sample disconnectivity graphs of PUBO energy landscapes and their different QUBO mappings accounting for both local minima and saddle regions. We demonstrate that QUBO energy landscape properties lead to the subpar performance for quadratic IMs and suggest directions for their improvement.
△ Less
Submitted 28 August, 2024; v1 submitted 2 March, 2024;
originally announced March 2024.
-
Memristor-based hardware and algorithms for higher-order Hopfield optimization solver outperforming quadratic Ising machines
Authors:
Mohammad Hizzani,
Arne Heittmann,
George Hutchinson,
Dmitrii Dobrynin,
Thomas Van Vaerenbergh,
Tinish Bhattacharya,
Adrien Renaudineau,
Dmitri Strukov,
John Paul Strachan
Abstract:
Ising solvers offer a promising physics-based approach to tackle the challenging class of combinatorial optimization problems. However, typical solvers operate in a quadratic energy space, having only pair-wise coupling elements which already dominate area and energy. We show that such quadratization can cause severe problems: increased dimensionality, a rugged search landscape, and misalignment w…
▽ More
Ising solvers offer a promising physics-based approach to tackle the challenging class of combinatorial optimization problems. However, typical solvers operate in a quadratic energy space, having only pair-wise coupling elements which already dominate area and energy. We show that such quadratization can cause severe problems: increased dimensionality, a rugged search landscape, and misalignment with the original objective function. Here, we design and quantify a higher-order Hopfield optimization solver, with 28nm CMOS technology and memristive couplings for lower area and energy computations. We combine algorithmic and circuit analysis to show quantitative advantages over quadratic Ising Machines (IM)s, yielding 48x and 72x reduction in time-to-solution (TTS) and energy-to-solution (ETS) respectively for Boolean satisfiability problems of 150 variables, with favorable scaling.
△ Less
Submitted 2 November, 2023;
originally announced November 2023.
-
Real phase structures on tropical manifolds and patchworks in higher codimension
Authors:
Johannes Rau,
Arthur Renaudineau,
Kris Shaw
Abstract:
This paper generalises the homeomorphism theorem behind Viro's combinatorial patchworking of hypersurfaces in toric varieties to arbitrary codimension using tropical geometry. We first define the patchwork of a polyhedral space equipped with a real phase structure. When the polyhedral subspace is tropically non-singular, we show that the patchwork is a topological manifold. When a non-singular tro…
▽ More
This paper generalises the homeomorphism theorem behind Viro's combinatorial patchworking of hypersurfaces in toric varieties to arbitrary codimension using tropical geometry. We first define the patchwork of a polyhedral space equipped with a real phase structure. When the polyhedral subspace is tropically non-singular, we show that the patchwork is a topological manifold. When a non-singular tropical variety appears as a tropical limit of a real analytic family, we show that the real part of a fibre of the family near the tropical limit is homeomorphic to the patchwork.
Finally we extend the spectral sequence introduced by the last two authors in the case of hypersurfaces to non-singular tropical varieties with real phase structures. As a corollary, we obtain bounds on the Betti numbers of the patchwork in terms of the dimensions of the tropical homology groups with coefficients modulo two.
△ Less
Submitted 12 October, 2023;
originally announced October 2023.
-
A Multimode Hybrid Memristor-CMOS Prototyping Platform Supporting Digital and Analog Projects
Authors:
Kamel-Eddine Harabi,
Clement Turck,
Marie Drouhin,
Adrien Renaudineau,
Thomas Bersani--Veroni,
Damien Querlioz,
Tifenn Hirtzlin,
Elisa Vianello,
Marc Bocquet,
Jean-Michel Portal
Abstract:
We present an integrated circuit fabricated in a process co-integrating CMOS and hafnium-oxide memristor technology, which provides a prototyping platform for projects involving memristors. Our circuit includes the periphery circuitry for using memristors within digital circuits, as well as an analog mode with direct access to memristors. The platform allows optimizing the conditions for reading a…
▽ More
We present an integrated circuit fabricated in a process co-integrating CMOS and hafnium-oxide memristor technology, which provides a prototyping platform for projects involving memristors. Our circuit includes the periphery circuitry for using memristors within digital circuits, as well as an analog mode with direct access to memristors. The platform allows optimizing the conditions for reading and writing memristors, as well as developing and testing innovative memristor-based neuromorphic concepts.
△ Less
Submitted 28 February, 2023;
originally announced February 2023.
-
Real phase structures on matroid fans and matroid orientations
Authors:
Johannes Rau,
Arthur Renaudineau,
Kris Shaw
Abstract:
We introduce the notion of real phase structure on rational polyhedral fans in Euclidean space. Such a structure consists of an assignment of affine spaces over $\mathbb{Z}/2\mathbb{Z}$ to each top dimensional face of the fan subject to two conditions. Given an oriented matroid we can construct a real phase structure on the fan of the underlying matroid. Conversely, we show that from a real phase…
▽ More
We introduce the notion of real phase structure on rational polyhedral fans in Euclidean space. Such a structure consists of an assignment of affine spaces over $\mathbb{Z}/2\mathbb{Z}$ to each top dimensional face of the fan subject to two conditions. Given an oriented matroid we can construct a real phase structure on the fan of the underlying matroid. Conversely, we show that from a real phase structure on a matroid fan we can produce an orientation of the underlying matroid. Thus real phase structures are cryptomorphic to matroid orientations. The topes of the orientated matroid are recovered immediately from the real phase structure. We also provide a direct way to recover the signed circuits of the oriented matroid from the real phase structure.
△ Less
Submitted 4 January, 2023; v1 submitted 16 June, 2021;
originally announced June 2021.
-
Patchworking the Log-critical locus of planar curves
Authors:
Lionel Lang,
Arthur Renaudineau
Abstract:
We establish a patchworking theorem à la Viro for the Log-critical locus of algebraic curves in $(\mathbb{C}^*)^2$. As an application, we prove the existence of projective curves of arbitrary degree with smooth connected Log-critical locus. To prove our patchworking theorem, we study the behaviour of Log-inflection points along families of curves defined by Viro polynomials. In particular, we prov…
▽ More
We establish a patchworking theorem �� la Viro for the Log-critical locus of algebraic curves in $(\mathbb{C}^*)^2$. As an application, we prove the existence of projective curves of arbitrary degree with smooth connected Log-critical locus. To prove our patchworking theorem, we study the behaviour of Log-inflection points along families of curves defined by Viro polynomials. In particular, we prove a generalisation of a theorem of Mikhalkin and the second author on the tropical limit of Log-inflection points.
△ Less
Submitted 25 March, 2021; v1 submitted 3 March, 2021;
originally announced March 2021.
-
Lefschetz section theorems for tropical hypersurfaces
Authors:
Charles Arnal,
Arthur Renaudineau,
Kristin Shaw
Abstract:
We establish variants of the Lefschetz hyperplane section theorem for the integral tropical homology groups of tropical hypersurfaces of toric varieties. It follows from these theorems that the integral tropical homology groups of non-singular tropical hypersurfaces which are compact or contained in $\mathbb{R}^n$ are torsion free. We prove a relationship between the coefficients of the $χ_y$ gene…
▽ More
We establish variants of the Lefschetz hyperplane section theorem for the integral tropical homology groups of tropical hypersurfaces of toric varieties. It follows from these theorems that the integral tropical homology groups of non-singular tropical hypersurfaces which are compact or contained in $\mathbb{R}^n$ are torsion free. We prove a relationship between the coefficients of the $χ_y$ genera of complex hypersurfaces in toric varieties and Euler characteristics of the integral tropical cellular chain complexes of their tropical counterparts. It follows that the integral tropical homology groups give the Hodge numbers of compact non-singular hypersurfaces of complex toric varieties. Finally for tropical hypersurfaces in certain affine toric varieties, we relate the ranks of their tropical homology groups to the Hodge-Deligne numbers of their complex counterparts.
△ Less
Submitted 15 July, 2019;
originally announced July 2019.
-
Bounding the Betti numbers of real hypersurfaces near the tropical limit
Authors:
Arthur Renaudineau,
Kristin Shaw
Abstract:
We prove a bound conjectured by Itenberg on the Betti numbers of real algebraic hypersurfaces near non-singular tropical limits. These bounds are given in terms of the Hodge numbers of the complexification. To prove the conjecture we introduce a real variant of tropical homology and define a filtration on the corresponding chain complex inspired by Kalinin's filtration. The spectral sequence assoc…
▽ More
We prove a bound conjectured by Itenberg on the Betti numbers of real algebraic hypersurfaces near non-singular tropical limits. These bounds are given in terms of the Hodge numbers of the complexification. To prove the conjecture we introduce a real variant of tropical homology and define a filtration on the corresponding chain complex inspired by Kalinin's filtration. The spectral sequence associated to this filtration converges to the homology groups of the real algebraic variety and we show that the terms of the first page are tropical homology groups with $\mathbb{Z}_2$-coefficients. The dimensions of these homology groups correspond to the Hodge numbers of complex projective hypersurfaces. The bounds on the Betti numbers of the real part follow, as well as a criterion to obtain a maximal variety. We also generalise a known formula relating the signature of the complex hypersurface and the Euler characteristic of the real algebraic hypersurface, as well as Haas' combinatorial criterion for the maximality of plane curves near the tropical limit.
△ Less
Submitted 12 November, 2019; v1 submitted 5 May, 2018;
originally announced May 2018.
-
Tropical limit of log-inflection points for planar curves
Authors:
Grigory Mikhalkin,
Arthur Renaudineau
Abstract:
The paper describes behavior of log-inflection points of curves in $(\mathbb{C}^*)^2$ under passing to the tropical limit. We show that such points accumulate by pairs at the midpoints of bounded edges in the limiting tropical curve. Log-inflection points are points of inflection with respect to the parallelization of $(\mathbb{C}^*)^2$ given by the multiplicative group law.
The paper describes behavior of log-inflection points of curves in $(\mathbb{C}^*)^2$ under passing to the tropical limit. We show that such points accumulate by pairs at the midpoints of bounded edges in the limiting tropical curve. Log-inflection points are points of inflection with respect to the parallelization of $(\mathbb{C}^*)^2$ given by the multiplicative group law.
△ Less
Submitted 15 December, 2017; v1 submitted 13 December, 2016;
originally announced December 2016.
-
Haas' theorem revisited
Authors:
Benoît Bertrand,
Erwan Brugallé,
Arthur Renaudineau
Abstract:
Haas' theorem describes all partchworkings of a given non-singular plane tropical curve $C$ giving rise to a maximal real algebraic curve. The space of such patchworkings is naturally a linear subspace $W_C$ of the $\mathbb{Z}/2\mathbb{Z}$-vector space $\overrightarrow Π_C$ generated by the bounded edges of $C$, and whose origin is the Harnack patchworking. The aim of this note is to provide an in…
▽ More
Haas' theorem describes all partchworkings of a given non-singular plane tropical curve $C$ giving rise to a maximal real algebraic curve. The space of such patchworkings is naturally a linear subspace $W_C$ of the $\mathbb{Z}/2\mathbb{Z}$-vector space $\overrightarrow Π_C$ generated by the bounded edges of $C$, and whose origin is the Harnack patchworking. The aim of this note is to provide an interpretation of affine subspaces of $\overrightarrow Π_C $ parallel to $W_C$. To this purpose, we work in the setting of abstract graphs rather than plane tropical curves. We introduce a topological surface $S_Γ$ above a trivalent graph $Γ$, and consider a suitable affine space $Π_Γ$ of real structures on $S_Γ$ compatible with $Γ$. We characterise $W_Γ$ as the vector subspace of $\overrightarrow Π_Γ$ whose associated involutions induce the same action on $H_1(S_Γ,\mathbb{Z}/2\mathbb{Z})$. We then deduce from this statement another proof of Haas' original result.
△ Less
Submitted 30 August, 2017; v1 submitted 7 September, 2016;
originally announced September 2016.
-
Real algebraic surfaces with many handles in $(\mathbb{CP}^1)^3$
Authors:
Arthur Renaudineau
Abstract:
In this text, we study Viro's conjecture and related problems for real algebraic surfaces in $(\mathbb{CP}^1)^3$. We construct a counter-example to Viro's conjecture in tridegree $(4,4,2)$ and a family of real algebraic surfaces of tridegree $(2k,2l,2)$ in $(\mathbb{CP}^1)^3$ with asymptotically maximal first Betti number of the real part. To perform such constructions, we consider double covers o…
▽ More
In this text, we study Viro's conjecture and related problems for real algebraic surfaces in $(\mathbb{CP}^1)^3$. We construct a counter-example to Viro's conjecture in tridegree $(4,4,2)$ and a family of real algebraic surfaces of tridegree $(2k,2l,2)$ in $(\mathbb{CP}^1)^3$ with asymptotically maximal first Betti number of the real part. To perform such constructions, we consider double covers of blow-ups of $(\mathbb{CP}^1)^2$ and we glue singular curves with special position of the singularities adapting the proof of Shustin's theorem for gluing singular hypersurfaces.
△ Less
Submitted 6 November, 2015;
originally announced November 2015.
-
A tropical construction of a family of real reducible curves
Authors:
Arthur Renaudineau
Abstract:
We give a constructive proof using tropical modifications of the existence of a family of real algebraic plane curves with asymptotically maximal numbers of even ovals.
We give a constructive proof using tropical modifications of the existence of a family of real algebraic plane curves with asymptotically maximal numbers of even ovals.
△ Less
Submitted 12 October, 2015;
originally announced October 2015.
-
A real sextic surface with 45 handles
Authors:
Arthur Renaudineau
Abstract:
It follows from classical restrictions on the topology of real algebraic varieties that the first Betti number of the real part of a real nonsingular sextic in $\mathbb{CP}^3$ can not exceed $94$. We construct a real nonsingular sextic $X$ in $\mathbb{CP}^3$ satisfying $b_1(\mathbb{R}X)=90$, improving a result of F.Bihan. The construction uses Viro's patchworking and an equivariant version of a de…
▽ More
It follows from classical restrictions on the topology of real algebraic varieties that the first Betti number of the real part of a real nonsingular sextic in $\mathbb{CP}^3$ can not exceed $94$. We construct a real nonsingular sextic $X$ in $\mathbb{CP}^3$ satisfying $b_1(\mathbb{R}X)=90$, improving a result of F.Bihan. The construction uses Viro's patchworking and an equivariant version of a deformation due to E.Horikawa.
△ Less
Submitted 13 December, 2014;
originally announced December 2014.
