In this contribution, we consider a zero-dimensional polynomial system in $n$ variables defined over a field $\mathbb{K}$. In the context of computing a Rational Univariate Representation (RUR) of its solutions, we address the problem of certifying a separating linear form and, once certified, calculating the RUR that comes from it, without any condition on the ideal else than being zero-dimensional. Our key result is that the RUR can be read (closed formula) from lexicographic Groebner bases of bivariate elimination ideals, even in the case where the original ideal that is not in shape position, so that one can use the same core as the well known FGLM method to propose a simple algorithm. Our first experiments, either with a very short code (300 lines) written in Maple or with a Julia code using straightforward implementations performing only classical Gaussian reductions in addition to Groebner bases for the degree reverse lexicographic ordering, show that this new method is already competitive with sophisticated state of the art implementations which do not certify the parameterizations.
相關內容
In this paper we consider the problem of estimating the $f$-moment ($\sum_{v\in [n]} (f(\mathbf{x}(v))-f(0))$) of a dynamic vector $\mathbf{x}\in \mathbb{G}^n$ over some abelian group $(\mathbb{G},+)$, where the $\|f\|_\infty$ norm is bounded. We propose a simple sketch and new estimation framework based on the \emph{Fourier transform} of $f$. I.e., we decompose $f$ into a linear combination of homomorphisms $f_1,f_2,\ldots$ from $(\mathbb{G},+)$ to $(\mathbb{C},\times)$, estimate the $f_k$-moment for each $f_k$, and synthesize them to obtain an estimate of the $f$-moment. Our estimators are asymptotically unbiased and have variance asymptotic to $\|\mathbf{x}\|_0^2 (\|f\|_\infty^2 m^{-1} + \|\hat{f}\|_1^2 m^{-2})$, where the size of the sketch is $O(m\log n\log|\mathbb{G}|)$ bits. When $\mathbb{G}=\mathbb{Z}$ this problem can also be solved using off-the-shelf $\ell_0$-samplers with space $O(m\log^2 n)$ bits, which does not obviously generalize to finite groups. As a concrete benchmark, we extend Ganguly, Garofalakis, and Rastogi's singleton-detector-based sampler to work over $\mathbb{G}$ using $O(m\log n\log|\mathbb{G}|\log(m\log n))$ bits. We give some experimental evidence that the Fourier-based estimation framework is significantly more accurate than sampling-based approaches at the same memory footprint.
Given a hypergraph $\mathcal{H}$, the dual hypergraph of $\mathcal{H}$ is the hypergraph of all minimal transversals of $\mathcal{H}$. The dual hypergraph is always Sperner, that is, no hyperedge contains another. A special case of Sperner hypergraphs are the conformal Sperner hypergraphs, which correspond to the families of maximal cliques of graphs. All these notions play an important role in many fields of mathematics and computer science, including combinatorics, algebra, database theory, etc. In this paper we study conformality of dual hypergraphs and prove several results related to the problem of recognizing this property. In particular, we show that the problem is in co-NP and can be solved in polynomial time for hypergraphs of bounded dimension. In the special case of dimension $3$, we reduce the problem to $2$-Satisfiability. Our approach has an implication in algorithmic graph theory: we obtain a polynomial-time algorithm for recognizing graphs in which all minimal transversals of maximal cliques have size at most $k$, for any fixed $k$.
Due to their flexibility to represent almost any kind of relational data, graph-based models have enjoyed a tremendous success over the past decades. While graphs are inherently only combinatorial objects, however, many prominent analysis tools are based on the algebraic representation of graphs via matrices such as the graph Laplacian, or on associated graph embeddings. Such embeddings associate to each node a set of coordinates in a vector space, a representation which can then be employed for learning tasks such as the classification or alignment of the nodes of the graph. As the geometric picture provided by embedding methods enables the use of a multitude of methods developed for vector space data, embeddings have thus gained interest both from a theoretical as well as a practical perspective. Inspired by trace-optimization problems, often encountered in the analysis of graph-based data, here we present a method to derive ellipsoidal embeddings of the nodes of a graph, in which each node is assigned a set of coordinates on the surface of a hyperellipsoid. Our method may be seen as an alternative to popular spectral embedding techniques, to which it shares certain similarities we discuss. To illustrate the utility of the embedding we conduct a case study in which analyse synthetic and real world networks with modular structure, and compare the results obtained with known methods in the literature.
Entropy conditions play a crucial role in the extraction of a physically relevant solution for a system of conservation laws, thus motivating the construction of entropy stable schemes that satisfy a discrete analogue of such conditions. TeCNO schemes (Fjordholm et al. 2012) form a class of arbitrary high-order entropy stable finite difference solvers, which require specialized reconstruction algorithms satisfying the sign property at each cell interface. Recently, third-order WENO schemes called SP-WENO (Fjordholm and Ray, 2016) and SP-WENOc (Ray, 2018) have been designed to satisfy the sign property. However, these WENO algorithms can perform poorly near shocks, with the numerical solutions exhibiting large spurious oscillations. In the present work, we propose a variant of the SP-WENO, termed as Deep Sign-Preserving WENO (DSP-WENO), where a neural network is trained to learn the WENO weighting strategy. The sign property and third-order accuracy are strongly imposed in the algorithm, which constrains the WENO weight selection region to a convex polygon. Thereafter, a neural network is trained to select the WENO weights from this convex region with the goal of improving the shock-capturing capabilities without sacrificing the rate of convergence in smooth regions. The proposed synergistic approach retains the mathematical framework of the TeCNO scheme while integrating deep learning to remedy the computational issues of the WENO-based reconstruction. We present several numerical experiments to demonstrate the significant improvement with DSP-WENO over the existing variants of WENO satisfying the sign property.
A graph $G$ is well-covered if all maximal independent sets are of the same cardinality. Let $w:V(G) \longrightarrow\mathbb{R}$ be a weight function. Then $G$ is $w$-well-covered if all maximal independent sets are of the same weight. An edge $xy \in E(G)$ is relating if there exists an independent set $S$ such that both $S \cup \{x\}$ and $S \cup \{y\}$ are maximal independent sets in the graph. If $xy$ is relating then $w(x)=w(y)$ for every weight function $w$ such that $G$ is $w$-well-covered. Relating edges play an important role in investigating $w$-well-covered graphs. The decision problem whether an edge in a graph is relating is NP-complete. We prove that the problem remains NP-complete when the input is restricted to graphs without cycles of length $6$. This is an unexpected result because recognizing relating edges is known to be polynomially solvable for graphs without cycles of lengths $4$ and $6$, graphs without cycles of lengths $5$ and $6$, and graphs without cycles of lengths $6$ and $7$. A graph $G$ belongs to the class $W_2$ if every two pairwise disjoint independent sets in $G$ are included in two pairwise disjoint maximum independent sets. It is known that if $G$ belongs to the class $W_2$, then it is well-covered. A vertex $v \in V(G)$ is shedding if for every independent set $S \subseteq V(G)-N[v]$, there exists a vertex $u \in N(v)$ such that $S \cup \{u\}$ is independent. Shedding vertices play an important role in studying the class $W_2$. Recognizing shedding vertices is co-NP-complete, even when the input is restricted to triangle-free graphs. We prove that the problem is co-NP-complete for graphs without cycles of length $6$.
For a locally finite set, $A \subseteq \mathbb{R}^d$, the $k$-th Brillouin zone of $a \in A$ is the region of points $x \in \mathbb{R}^d$ for which $\|x-a\|$ is the $k$-th smallest among the Euclidean distances between $x$ and the points in $A$. If $A$ is a lattice, the $k$-th Brillouin zones of the points in $A$ are translates of each other, which tile space. Depending on the value of $k$, they express medium- or long-range order in the set. We study fundamental geometric and combinatorial properties of Brillouin zones, focusing on the integer lattice and its perturbations. Our results include the stability of a Brillouin zone under perturbations, a linear upper bound on the number of chambers in a zone for lattices in $\mathbb{R}^2$, and the convergence of the maximum volume of a chamber to zero for the integer lattice.
Consider a matroid where all elements are labeled with an element in $\mathbb{Z}$. We are interested in finding a base where the sum of the labels is congruent to $g \pmod m$. We show that this problem can be solved in $\tilde{O}(2^{4m} n r^{5/6})$ time for a matroid with $n$ elements and rank $r$, when $m$ is either the product of two primes or a prime power. The algorithm can be generalized to all moduli and, in fact, to all abelian groups if a classic additive combinatorics conjecture by Schrijver and Seymour holds true. We also discuss the optimization version of the problem.
Given an intractable distribution $p$, the problem of variational inference (VI) is to compute the best approximation $q$ from some more tractable family $\mathcal{Q}$. Most commonly the approximation is found by minimizing a Kullback-Leibler (KL) divergence. However, there exist other valid choices of divergences, and when $\mathcal{Q}$ does not contain~$p$, each divergence champions a different solution. We analyze how the choice of divergence affects the outcome of VI when a Gaussian with a dense covariance matrix is approximated by a Gaussian with a diagonal covariance matrix. In this setting we show that different divergences can be \textit{ordered} by the amount that their variational approximations misestimate various measures of uncertainty, such as the variance, precision, and entropy. We also derive an impossibility theorem showing that no two of these measures can be simultaneously matched by a factorized approximation; hence, the choice of divergence informs which measure, if any, is correctly estimated. Our analysis covers the KL divergence, the R\'enyi divergences, and a score-based divergence that compares $\nabla\log p$ and $\nabla\log q$. We empirically evaluate whether these orderings hold when VI is used to approximate non-Gaussian distributions.
This study introduces the syntropy function ($S_N$) and expectancy function ($E_N$), derived from the novel function $\phi$, to provide a refined perspective on complexity, extending beyond conventional entropy analysis. $S_N$ is designed to detect localized coherent events, whereas $E_N$ encapsulates expected system behaviors, offering a comprehensive framework for understanding system dynamics. The manuscript explores essential theorems and properties, underscoring their theoretical and practical implications. Future research will further elucidate their roles, particularly in biological signals and dynamic systems, suggesting a deep interplay between order and chaos.
PyTorch \texttt{2.x} introduces a compiler designed to accelerate deep learning programs. However, for machine learning researchers, adapting to the PyTorch compiler to full potential can be challenging. The compiler operates at the Python bytecode level, making it appear as an opaque box. To address this, we introduce \texttt{depyf}, a tool designed to demystify the inner workings of the PyTorch compiler. \texttt{depyf} decompiles bytecode generated by PyTorch back into equivalent source code, and establishes connections between in-memory code objects and their on-disk source code counterparts. This feature enables users to step through the source code line by line using debuggers, thus enhancing their understanding of the underlying processes. Notably, \texttt{depyf} is non-intrusive and user-friendly, primarily relying on two convenient context managers for its core functionality. The project is \href{//github.com/thuml/depyf}{ openly available} and is recognized as a \href{//pytorch.org/ecosystem/}{PyTorch ecosystem project}.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191