Although the positivity of a quartic polynomial is a well-researched topic, existing conditions are often highly complex. Some necessary and sufficient conditions for the positivity of a quartic polynomial are presented through a separation method based on Ferrari's technique of solving a quartic equation. We apply the result to the problem of the projection of the coefficient space.
Moosbauer and Poole have recently shown that the multiplication of two $5\times 5$ matrices requires no more than 93 multiplications in the (possibly non-commutative) coefficient ring, and that the multiplication of two $6\times 6$ matrices requires no more than 153 multiplications. Taking these multiplication schemes as starting points, we found improved matrix multiplication schemes for various rectangular matrix formats using a flip graph search.
We present efficient methods for calculating linear recurrences of hypergeometric double sums and, more generally, of multiple sums. In particular, we supplement this approach with the algorithmic theory of contiguous relations, which guarantees the applicability of our method for many input sums. In addition, we elaborate new techniques to optimize the underlying key task of our method to compute rational solutions of parameterized linear recurrences.
The notion of lacunary infinite numerical sequence is introduced. It is shown that for an arbitrary linear difference operator L with coefficients belonging to the set R of infinite numerical sequences, a criterion (i.e., a necessary and sufficient condition) for the infinite dimensionality of its space $V_L$ of solutions belonging to R is the presence of a lacunary sequence in $V_L$.
In this short note, we reprove in a very elementary way some known facts about Pisano periods as well as some considerations about the link between Pisano periods and the order of roots of the characteristic equation. The technics only requires a small background in ring theory (merely the definition of a commutative ring). The tools set here can be reused for all linear recurrences with quadratic non-constant characteristic equation.
This paper is about solving polynomial systems. It first recalls how to do that efficiently with a very high probability of correctness by reconstructing a rational univariate representation (rur) using Groebner revlex computation, Berlekamp-Massey algorithm and Hankel linear system solving modulo several primes in parallel. Then it introduces a new method (theorem \ref{prop:check}) for rur certification that is effective for most polynomial systems.These algorithms are implemented in https://www-fourier.univ-grenoble-alpes.fr/~parisse/giac.html since version 1.7.0-13 or 1.7.0-17 for certification, it has (July 2021) leading performances on multiple CPU, at least for an open-source software.
Given a lattice L in Z^m and a subset A of R^m, we say that a point in A is lonely if it is not equivalent modulo L to another point of A. We are interested in identifying lonely points for specific choices of L when A is a dilated standard simplex, and in conditions on L which ensure that the number of lonely points is unbounded as the simplex dilation goes to infinity.
The article considers linear functions of many (n) variables - multilinear polynomials (MP). The three-steps evaluation is presented that uses the minimal possible number of floating point operations for non-sparse MP at each step. The minimal number of additions is achieved in the algorithm for fast MP derivatives (FMPD) calculation. The cost of evaluating all first derivatives approaches to only 1/8 of MP evaluation with a growing number of variables. The FMPD algorithm structure exhibits similarity to the Fast Fourier Transformation (FFT) algorithm.
For a finite separable field extension K/k, all subfields can be obtained by intersecting so-called principal subfields of K/k. In this work we present a way to quickly compute these intersections. If the number of subfields is high, then this leads to faster run times and an improved complexity.
In this paper, we are concerned with the problem of determining the existence of multiple equilibria in economic models. We propose a general and complete approach for identifying multiplicities of equilibria in semi-algebraic economies, which may be expressed as semi-algebraic systems. The approach is based on triangular decomposition and real solution classification, two powerful tools of algebraic computation. Its effectiveness is illustrated by two examples of application.
We present a detailed and simplified version of Hrushovski's algorithm that determines the Galois group of a linear differential equation. There are three major ingredients in this algorithm. The first is to look for a degree bound for proto-Galois groups, which enables one to compute one of them. The second is to determine the identity component of the Galois group that is the pullback of a torus to the proto-Galois group. The third is to recover the Galois group from its identity component and a finite Galois group.
Given the equations of the first and the second order surfaces in multidimensional space, our goal is to construct a univariate polynomial one of the zeros of which coincides with the square of the distance between these surfaces. To achieve this goal we employ Elimination Theory methods. The proposed approach is also extended for the case of parameter dependent surfaces.
We present an algorithm for tests generation tools based on symbolic execution. The algorithm is supposed to help in situations, when a tool is repeatedly failing to cover some code by tests. The algorithm then provides the tool a necessary condition strongly narrowing space of program paths, which must be checked for reaching the uncovered code. We also discuss integration of the algorithm into the tools and we provide experimental results showing a potential of the algorithm to be valuable in the tools, when properly implemented there.
We present a novel method for checking the Hurwitz stability of a polytope of matrices. First we prove that the polytope matrix is stable if and only if two homogenous polynomials are positive on a simplex, then through a newly proposed method, i.e., the weighted difference substitution method, the latter can be checked in finite steps. Examples show the efficiency of our method.
The famous F5 algorithm for computing \gr basis was presented by Faugère in 2002. The original version of F5 is given in programming codes, so it is a bit difficult to understand. In this paper, the F5 algorithm is simplified as F5B in a Buchberger's style such that it is easy to understand and implement. In order to describe F5B, we introduce F5-reduction, which keeps the signature of labeled polynomials unchanged after reduction. The equivalence between F5 and F5B is also shown. At last, some versions of the F5 algorithm are illustrated.
A Chebyshev expansion is a series in the basis of Chebyshev polynomials of the first kind. When such a series solves a linear differential equation, its coefficients satisfy a linear recurrence equation. We interpret this equation as the numerator of a fraction of linear recurrence operators. This interpretation lets us give a simple view of previous algorithms, analyze their complexity, and design a faster one for large orders.
Given an n x n matrix over the ring of differential polynomials F(t)[\D;δ], we show how to compute the Hermite form H of A, and a unimodular matrix U such that UA=H. The algorithm requires a polynomial number of operations in terms of n, deg_D(A), and deg_t(A). When F is the field of rational numbers, it also requires time polynomial in the bit-length of the coefficients.
We discuss efficient conversion algorithms for orthogonal polynomials. We describe a known conversion algorithm from an arbitrary orthogonal basis to the monomial basis, and deduce a new algorithm of the same complexity for the converse operation.
AbstractCs4[Sc6C]Cl13 (tetragonal, I41/amd; a = 1 540,5(4); c = 1 017,9(7) pm; c/a = 0,661; Z = 4; R = 0,038; Rw = 0,026 und Cs4[Pr6(C2)]I13 (a = 1 804,9(3); c = 1 259,5(3) pm; c/a = 0,698; R = 0,106; Rw = 0,068) werden bei der metallothermischen Reduktion von ScCl3 bzw. PrI3 mit Caesium in Gegenwart von Kohlenstoff in verschweißten Tantalampullen in Form von grünschwarzen bzw. blauschwarzen, messingglänzenden Einkristallen erhalten. Die weitgehend isotypen Kristallstrukturen enthalten isolierte [Sc6C]‐ bzw. [Pr6(C2)]‐Cluster, die von 18 Halogenid‐Ionen (X−, 12 Xi und 6 Xa; X = Cl bzw. I) umgeben sind. Die Verknüpfung erfolgt gemäß dem Motiv [M6Z]XXXX (M = Sc bzw. Pr; Z = C bzw. C2) und stellt damit ein noch unbekanntes Verknüpfungsmuster für Verbindungen der Zusammensetzung Ax[M6Z]X13 dar, das jenem der [TiO6]‐Oktaeder in der Anatas‐Struktur von TiO2 entspricht.
This note presents absolute bounds on the size of the coefficients of the characteristic and minimal polynomials depending on the size of the coefficients of the associated matrix. Moreover, we present algorithms to compute more precise input-dependant bounds on these coefficients. Such bounds are e.g. useful to perform deterministic chinese remaindering of the characteristic or minimal polynomial of an integer matrix.