Search

Some time in the early 2000's, I extended the routine CompanionMatrix in the LinearAlgebra package to compute what are called linearizations of matrix polynomials. These are just univariate polynomials with matrix coefficients; isomorphically, these are matrices with univariate polynomial entries. Linearizations can be used to solve multivariate systems of equations by a number of techniques, which are "well-known" in the sense that they are in books and papers. However "well-known" they are, they deserve to be better-known, and this expository paper gives examples of some of the methods that can be used. Think of this as an extended help page for the code (which, if I am honest, is long overdue for an upgrade). [ABSTRACT FROM AUTHOR]

Approximate polynomial GCD (greatest common divisor) of polynomials with a priori errors on their coefficients, is one of interesting problems in Symbolic-Numeric Computations. In fact, there are many known algorithms: QRGCD, UVGCD, STLN based methods, Fastgcd and so on. The fundamental question of this paper is "which is the best?" from the practical point of view, and subsequently "is there any better way?" by any small extension, any effect by pivoting, and any combination of sub-routines along the algorithms. In this paper, we consider a framework that covers those algorithms and their sub-routines, and makes their sub-routines being interchangeable between the algorithms (i.e. disassembling the algorithms and reassembling their parts). By this framework along with/without small new extensions and a newly adapted refinement sub-routine, we have done many performance tests and found the current answer. In summary, 1) UVGCD is the best way to get smaller tolerance, 2) modified Fastgcd is better for GCD that has one or more clusters of zeros with large multiplicity, and 3) modified ExQRGCD is better for GCD that has no cluster of zeros. [ABSTRACT FROM AUTHOR]

We show that an algorithm established in a recent publication in this journal to provide a fraction-free version for the Bistritz test can also be used to compute the unit-circle resultant. The consequence is an effective new algorithm to find this resultant for any complex polynomial that is also an efficient integer algorithm for polynomial with real or Gaussian integer coefficients. The algorithm ends always with the resultant expressed as the minimal degree multivariate polynomial of the polynomial's (indeterminate) coefficients. A simpler form of the algorithm, that equally reaches this expression in all circumstances, but is not guaranteed to stay over integers during possible intermediate abnormal gaps, is also suggested along with the simplest form that the algorithm takes in the strongly regular case. [ABSTRACT FROM AUTHOR]

This paper revisits the Bézout, Sylvester, and power-basis matrix representations of the greatest common divisor (GCD) of sets of several polynomials. Furthermore, the present work introduces the application of the QR decomposition with column pivoting to a Bézout matrix achieving the computation of the degree and the coeffcients of the GCD through the range of the Bézout matrix. A comparison in terms of computational complexity and numerical effciency of the Bézout-QR, Sylvester-QR, and subspace-SVD methods for the computation of theGCDof sets of several polynomials with real coeffcients is provided.Useful remarks about the performance of the methods based on computational simulations of sets of several polynomials are also presented.

In this paper, we consider the problem of counting algebraic numbers α of fixed degree n and bounded height Q such that the derivative of the minimal polynomial P α (x) of α is bounded, P α ′ (α) < Q 1 − v . This problem has many applications to the problems of metric theory of Diophantine approximation. We prove that the number of α defined above on the interval − 1 2 , 1 2 does not exceed c 1 (n) Q n + 1 − 1 7 v for Q > Q 0 (n) and 1. 4 ≤ v ≤ 7 1 6 (n + 1). Our result is based on an improvement to a lemma from Gelfond's monograph "Transcendental and algebraic numbers". Given an integer polynomial small enough in some point, the lemma provides an upper bound for the absolute value of its irreducible divisor. We obtain a stronger estimate which holds in real points located far enough from all algebraic numbers of bounded degree and height. This is done by considering the resultant of two polynomials represented as the determinant of the Sylvester matrix for the shifted counterparts. [ABSTRACT FROM AUTHOR]

Computing the greatest common divisor of a set of polynomials is a problem which plays an important role in different fields, such as linear system, control, and network theory. In practice, the polynomials are obtained through measurements and computations, so that their coefficients are inexact. This poses the problem of computing an approximate common factor. We propose an improvement and a generalization of the method recently proposed in Guglielmi et al. (SIAM J. Numer. Anal. 55, 1456–1482, 2017), which restates the problem as a (structured) distance to singularity of the Sylvester matrix. We generalize the algorithm in order to work with more than 2 polynomials and to compute an Approximate GCD (Greatest Common Divisor) of degree k ≥ 1; moreover, we show that the algorithm becomes faster by replacing the eigenvalues by the singular values. [ABSTRACT FROM AUTHOR]

This paper presents a new algorithm for computing the extended Hensel construction (EHC) of multivariate polynomials in main variable x and sub-variables u1, u2, · · ·, um over a number field K. This algorithm first constructs a set by using the resultant of two initial coprime factors w.r.t. x, and then obtains the Hensel factors by comparing the coefficients of xi on both sides of an equation. Since the Hensel factors are polynomials of the main variable with coefficients in fraction field K(u1, u2, · · ·, um), the computation cost of handling rational functions can be high. Therefore, the authors use a method which multiplies resultant and removes the denominators of the rational functions. Unlike previously-developed algorithms that use interpolation functions or Gröbner basis, the algorithm relies little on polynomial division, and avoids multiplying by different factors when removing the denominators of Hensel factors. All algorithms are implemented using Magma, a computational algebra system and experiments indicate that our algorithm is more efficient. [ABSTRACT FROM AUTHOR]

Blind image deconvolution (BID) is one of the most important problems in image processing, and it requires the determination of an exact image F from a degraded form of it G when little or no information about F and the point spread function (PSF) H is known. Several methods have been developed for the solution of this problem, and one class of methods considers F,G and H to be bivariate polynomials in which the polynomial computations are implemented by the Sylvester or Bézout resultant matrices. This paper compares these matrices for the solution of the problem of BID, and it is shown that it reduces to a comparison of their effectiveness for greatest common divisor (GCD) computations. This is a difficult problem because the determination of the degree of the GCD of two polynomials requires the calculation of the rank of a matrix, and this rank determines the size of the PSF. It is shown that although the Bézout matrix is symmetric (unlike the Sylvester matrix) and it is smaller than the Sylvester matrix, which has computational advantages, it yields consistently worse results than the Sylvester matrix for the size and coefficients of the PSF. Computational examples of blurred and deblurred images obtained with the Sylvester and Bézout matrices are shown, and the superior results obtained with the Sylvester matrix are evident. [ABSTRACT FROM AUTHOR]

In this survey paper, a summary of results which are to be found in a series of papers, is presented. The subject of interest is focused on matrix algebraic properties of the Fisher information matrix (FIM) of stationary processes. The FIM is an ingredient of the Cram´er-Rao inequality, and belongs to the basics of asymptotic estimation theory in mathematical statistics. The FIM is interconnected with the Sylvester, Bezout and tensor Sylvester matrices. Through these interconnections it is shown that the FIM of scalar and multiple stationary processes fulfill the resultant matrix property. A statistical distance measure involving entries of the FIM is presented. In quantum information, a different statistical distance measure is set forth. It is related to the Fisher information but where the information about one parameter in a particular measurement procedure is considered. The FIM of scalar stationary processes is also interconnected to the solutions of appropriate Stein equations, conditions for the FIM to verify certain Stein equations are formulated. The presence of Vandermonde matrices is also emphasized.

We define Sylvester-Padovan-Jacobsthal-type sequences of the first and second kinds via the Sylvester matrices which are obtained from the characteristic polynomials of Padovan and Jacobsthal sequences, and then we give miscellaneous properties of these sequences. Also, we obtain cyclic groups and semigroups from the multiplicative order of the generator matrices of the Sylvester-Padovan-Jacobsthal-type sequences of the first-kind and second-kind modulo m. Then we derive relationships between the orders of the cyclic groups obtained and the periods of these sequences modulo m. [ABSTRACT FROM AUTHOR]

The problem of computing the distance of two real coprime polynomials to the set of polynomials with a nontrivial greatest common divisor (GCD) appears in computer algebra, signal processing, and control theory. It has been studied in the literature under the names approximate common divisor, ε-GCD, and distance to uncontrollability. Existing solution methods use di erent types of local optimization methods and require a user-defined initial approximation. In this paper, we propose a new method that allows us to include constraints on the coefficients of the polynomials. Moreover, the method proposed in the paper is more robust to the initial approximation than the Newton-type optimization methods available in the literature. Our approach consists of two steps: (1) reformulate the problem as a problem of determining the structured distance to singularity of an associated Sylvester matrix, and (2) integrate a system of ODEs, which describes the gradient associated to the functional to be minimized. [ABSTRACT FROM AUTHOR]

The resultant theory plays a crucial role in computational algebra and algebraic geometry. The theory has two aspects: algebraic and geometric. In this paper, we focus on the algebraic aspect. One of the most important and well known algebraic properties of the resultant is that it is equal to the determinant of the Sylvester matrix. In 2008, Odagiri proved that a similar property holds over the tropical semiring if one replaces subtraction with addition. The tropical semiring belongs to a large family of algebraic structures called commutative idempotent semiring. In this paper, we prove that the same property (with subtraction replaced with addition) holds over an arbitrary commutative idempotent semiring. [ABSTRACT FROM AUTHOR]