For systems of polynomial equations, we study the problem of computing the Newton polytope of their eliminants. As was shown by Esterov and Khovanskii, such Newton polytopes are mixed fiber polytopes of the Newton polytopes of the input equations. We use their results in combination with mixed subdivisions to design an algorithm computing these special polytopes. We demonstrate the increase in practical performance of our algorithm compared to existing methods using tropical geometry and discuss the differences that lead to this increase in performance. We also demonstrate an application of our work to differential elimination.
Arthur R. C. McCray, Tao Zhou, Saugat Kandel
et al.
AbstractThe manipulation and control of nanoscale magnetic spin textures are of rising interest as they are potential foundational units in next-generation computing paradigms. Achieving this requires a quantitative understanding of the spin texture behavior under external stimuli using in situ experiments. Lorentz transmission electron microscopy (LTEM) enables real-space imaging of spin textures at the nanoscale, but quantitative characterization of in situ data is extremely challenging. Here, we present an AI-enabled phase-retrieval method based on integrating a generative deep image prior with an image formation forward model for LTEM. Our approach uses a single out-of-focus image for phase retrieval and achieves significantly higher accuracy and robustness to noise compared to existing methods. Furthermore, our method is capable of isolating sample heterogeneities from magnetic contrast, as shown by application to simulated and experimental data. This approach allows quantitative phase reconstruction of in situ data and can also enable near real-time quantitative magnetic imaging.
The cylindrical algebraic covering method was originally proposed to decide the satisfiability of a set of non-linear real arithmetic constraints. We reformulate and extend the cylindrical algebraic covering method to allow for checking the truth of arbitrary non-linear arithmetic formulas, adding support for both quantifiers and Boolean structure. Furthermore, we also propose a variant to perform quantifier elimination on such formulas. After introducing the algorithm, we elaborate on various extensions, optimizations and heuristics. Finally, we present an experimental evaluation of our implementation and provide a comparison with state-of-the-art SMT solvers and quantifier elimination tools.
AimsBovine respiratory disease (BRD) has serious impacts on dairy production and animal welfare. It is most commonly diagnosed based on clinical respiratory signs (CRS), but in recent years, thoracic ultrasonography (TUS) has emerged as a diagnostic tool with improved sensitivity and specificity. This study aimed to assess the alignment of BRD diagnoses based on a Clinical Respiratory Scoring Chart (CRSC) and weekly TUS findings throughout the progression of BRD of variable severity in preweaned Holstein dairy heifers.MethodsA total of 60 calves on two farms were followed from the 2nd week of life through the 11th week of life and assessed on a weekly basis for CRS and lung consolidation via TUS. The alignment of BRD diagnoses based on CRSC scores and TUS findings was evaluated across disease progression (pre‐consolidation, onset, chronic, or recovered) and severity (lobular or lobar lung consolidation) using receiver operator curves and area under the curves combined with Cohen's kappa (κ), sensitivity, and specificity.ResultsThe diagnosis of BRD using CRSC scores ≥5 aligned best with the onset of lobar lung consolidation (>1 cm in width and full thickness). This equated to an acceptable level of discrimination (AUC = 0.76), fair agreement (κ = 0.37), and a sensitivity of 29% and specificity of 99%. Similarly, there was acceptable discrimination (AUC = 0.70) and fair agreement (κ = 0.33) between CRSC ≥5 and the onset of a less severe threshold of disease based on lobular (1–3 cm2 but not full thickness) or lobar consolidation. Discrimination remained acceptable (AUC = 0.71) with fair agreement (κ = 0.28) between CRSC scores ≥2 for nasal discharge and/or cough (spontaneous or induced) and the onset of lobar consolidation. However, sensitivity was <40% across comparisons and outside of the onset of disease there tended to be poor discrimination, slight agreement, and lowered sensitivity between CRS and TUS diagnoses of lobular or lobar consolidation (pre‐consolidation, chronic, or recovered). Conversely, specificity was relatively high (≥92%) across comparisons suggesting that CRSC diagnoses indicative of BRD and associated lung consolidation tend to result in few false positive diagnoses and accurate identification of healthy animals.Conclusions and clinical relevanceAlthough we found the specificity of clinical signs for diagnosing lung consolidation to be ≥92% across all methods of TUS evaluations, the low levels of sensitivity dictate that clinical assessments lead to many false negative diagnoses. Consequently, depending on clinical signs alone to diagnose BRD within populations of dairy calves will likely result in overlooking a substantial proportion of subclinically affected animals that could inform the success of treatment and prevention protocols and guide management decisions.
A Gröbner basis computation for the Weyl algebra with respect to a tropical term order and by using a homogenization-dehomogenization technique is sufficiently sluggish. A significant number of reductions to zero occur. To improve the computation, a tropical F5 algorithm is developed for this context. As a member of the family of signature-based algorithms, this algorithm keeps track of where Weyl algebra elements come from to anticipate reductions to zero. The total order for ordering module monomials or signatures in this paper is designed as close as possible to the definition of the tropical term order. As in Vaccon et al. (2021), this total order is not compatible with the tropical term order.
Cylindrical Algebraic Decomposition (CAD) by projection and lifting requires many iterated univariate resultants. It has been observed that these often factor, but to date this has not been used to optimise implementations of CAD. We continue the investigation into such factorisations, writing in the specific context of SC-Square.
Let $\mathbb{K}[x_1, \dots, x_n]$ be a multivariate polynomial ring over a field $\mathbb{K}$. Let $(u_1, \dots, u_n)$ be a sequence of $n$ algebraically independent elements in $\mathbb{K}[x_1, \dots, x_n]$. Given a polynomial $f$ in $\mathbb{K}[u_1, \dots, u_n]$, a subring of $\mathbb{K}[x_1, \dots, x_n]$ generated by the $u_i$'s, we are interested infinding the unique polynomial $f_{\rm new}$ in $\mathbb{K}[e_1,\dots, e_n]$, where $e_1, \dots, e_n$ are new variables, such that $f_{\mathrm{new}}(u_1, \dots, u_n) = f(x_1, \dots, x_n)$. We provide an algorithm and analyze its arithmetic complexity to compute $f_{\mathrm{new}}$ knowing $f$ and $(u_1, \dots, u_n)$.
Some aspects of Computer Algebra (notably Computation Group Theory and Computational Number Theory) have some good databases of examples, typically of the form "all the X up to size n". But most of the others, especially on the polynomial side, are lacking such, despite the utility they have demonstrated in the related fields of SAT and SMT solving. We claim that the field would be enhanced by such community-maintained databases, rather than each author hand-selecting a few, which are often too large or error-prone to print, and therefore difficult for subsequent authors to reproduce.
This paper focuses on the problem of reconstructing a vector of rational functions given some evaluations, or more generally given their remainders modulo different polynomials. The special case of rational functions sharing the same denominator, a.k.a.Simultaneous Rational Function Reconstruction (SRFR), has many applications from linear system solving to coding theory, provided that SRFR has a unique solution. The number of unknowns in SRFR is smaller than for a general vector of rational function. This allows to reduce the number of evaluation points needed to guarantee the existence of a solution, but we may lose its uniqueness. In this work, we prove that uniqueness is guaranteed for a generic instance.
We develop algorithms for certifying an approximation to a nonsingular solution of a square system of equations built from univariate analytic functions. These algorithms are based on the existence of oracles for evaluating basic data about the input analytic functions. One approach for certification is based on alpha-theory while the other is based on the Krawczyk generalization of Newton's iteration. We show that the necessary oracles exist for D-finite functions and compare the two algorithmic approaches for this case using our software implementation in SageMath.
We present a randomized quantum algorithm for polynomial factorization over finite fields. For polynomials of degree $n$ over a finite field $\F_q$, the average-case complexity of our algorithm is an expected $O(n^{1 + o(1)} \log^{2 + o(1)}q)$ bit operations. Only for a negligible subset of polynomials of degree $n$ our algorithm has a higher complexity of $O(n^{4 / 3 + o(1)} \log^{2 + o(1)}q)$ bit operations. This breaks the classical $3/2$-exponent barrier for polynomial factorization over finite fields \cite{guo2016alg}.
Hilbert order is widely applied in many areas. However, most of the algorithms are confined to low dimensional cases. In this paper, algorithms for encoding and decoding arbitrary dimensional Hilbert order are presented. Eight algorithms are proposed. Four algorithms are based on arithmetic operations and the other four algorithms are based on bit operations. For the algorithms complexities, four of them are linear and the other four are constant for given inputs. In the end of the paper, algorithms for two dimensional Hilbert order are presented to demonstrate the usage of the algorithms introduced.
AbstractCo-expression analysis reveals useful dysregulation patterns of gene cooperativeness for understanding cancer biology and identifying new targets for treatment. We developed a structural strategy to identify co-expressed gene networks that are important for chronic myelogenous leukemia (CML). This strategy compared the distributions of expressional correlations between CML and normal states and it identified a data-driven threshold to classify strongly co-expressed networks that had the best coherence with CML. Using this strategy, we found a transcriptome-wide reduction of co-expression connectivity in CML, reflecting potentially loosened molecular regulation. Conversely, when we focused on nucleophosmin 1 (NPM1) associated networks, NPM1 established more co-expression linkages with BCR-ABL pathways and ribosomal protein networks in CML than normal. This finding implicates a new role of NPM1 in conveying tumorigenic signals from the BCR-ABL oncoprotein to ribosome biogenesis, affecting cellular growth. Transcription factors may be regulators of the differential co-expression patterns between CML and normal.
In this paper, we extend the idea of comprehensive Gröbner bases given by Weispfenning (1992) to border bases for zero dimensional parametric polynomial ideals. For this, we introduce a notion of comprehensive border bases and border system, and prove their existence even in the cases where they do not correspond to any term order. We further present algorithms to compute comprehensive border bases and border system. Finally, we study the relation between comprehensive Gröbner bases and comprehensive border bases w.r.t. a term order and give an algorithm to compute such comprehensive border bases from comprehensive Gröbner bases.
In this paper, we propose an incremental algorithm for computing cylindrical algebraic decompositions. The algorithm consists of two parts: computing a complex cylindrical tree and refining this complex tree into a cylindrical tree in real space. The incrementality comes from the first part of the algorithm, where a complex cylindrical tree is constructed by refining a previous complex cylindrical tree with a polynomial constraint. We have implemented our algorithm in Maple. The experimentation shows that the proposed algorithm outperforms existing ones for many examples taken from the literature.
The classical division algorithm for polynomials requires $O(n^2)$ operations for inputs of size $n$. Using reversal technique and Newton iteration, it can be improved to $O({M}(n))$, where ${M}$ is a multiplication time. But the method requires that the degree of the modulo, $x^l$, should be the power of 2. If $l$ is not a power of 2 and $f(0)=1$, Gathen and Gerhard suggest to compute the inverse,$f^{-1}$, modulo $x^{\lceil l/2^r\rceil}, x^{\lceil l/2^{r-1}\rceil},..., x^{\lceil l/2\rceil}, x^l$, separately. But they did not specify the iterative step. In this note, we show that the original Newton iteration formula can be directly used to compute $f^{-1}\,{mod}\,x^{l}$ without any additional cost, when $l$ is not a power of 2.
We give an algebraic quantifier elimination algorithm for the first-order theory over any given finite field using Gröbner basis methods. The algorithm relies on the strong Nullstellensatz and properties of elimination ideals over finite fields. We analyze the theoretical complexity of the algorithm and show its application in the formal analysis of a biological controller model.
Given the implicit equation $F(x,y,t,s)$ of a family of algebraic plane curves depending on the parameters $t,s$, we provide an algorithm for studying the topology types arising in the family. For this purpose, the algorithm computes a finite partition of the parameter space so that the topology type of the family stays invariant over each element of the partition. The ideas contained in the paper can be seen as a generalization of the ideas in \cite{JGRS}, where the problem is solved for families of algebraic curves depending on one parameter, to the two-parameters case.
Let G=Aut_K (K(x)) be the Galois group of the transcendental degree one pure field extension K(x)/K. In this paper we describe polynomial time algorithms for computing the field Fix(H) fixed by a subgroup H < G and for computing the fixing group G_f of a rational function f in K(x).