Computation of connection coefficients and measure modifications for orthogonal polynomials

We observe that polynomial measure modifications for families of univariate orthogonal polynomials imply sparse connection coefficient relations. We therefore propose connecting L ² expansion coefficients between a polynomial family and a modified family by a sparse transformation. Accuracy and conditioning of the connection and its inverse are explored. The connection and recurrence coefficients can simultaneously be obtained as the Cholesky decomposition of a matrix polynomial involving the Jacobi matrix; this property extends to continuous, non-polynomial measure modifications on finite intervals. We conclude with an example of a useful application to families of Jacobi polynomials with parameters (γ,δ) where the fast Fourier transform may be applied in order to obtain expansion coefficients whenever 2γ and 2δ are odd integers.     

Interpolation of Sparse Multivariate Polynomials over Large Finite Fields with Applications

We develop a Las Vegas-randomized algorithm which performs interpolation of sparse multivariate polynomials over finite fields. Our algorithm can be viewed as the first successful adaptation of the sparse polynomial interpolation algorithm for the complex field developed by M. Ben-Or and P. Tiwari (1988, in “Proceedings of the 20th ACM Symposium on the Theory of Computing,” pp. 301–309, Assoc. Comput. Mach., New York) to the case of finite fields. It improves upon a previous result by D. Y. Grigoriev, M. Karpinski, and M. F. Singer (1990, SIAM J. Comput.19, 1059–1063) and is by far the most time efficient algorithm (time and processor efficient parallel algorithm) for the problem when the finite field is large. As applications, we obtain Monte Carlo-randomized parallel algorithms for sparse multivariate polynomial factorization and GCD over finite fields. The efficiency of these algorithms improves upon that of the previously known algorithms for the respective problems.     

On polynomial reciprocity law

The well-known law of quadratic reciprocity has over 150 proofs in print. We establish a relation between polynomial Jacobi symbols and resultants of polynomials over finite fields. Using this relation, we prove the polynomial reciprocity law and obtain a polynomial analogue of classical Burde's quartic reciprocity law. Under the use of our polynomial Poisson summation formula and the evaluation of polynomial exponential map, we get a reciprocity for the generalized polynomial quadratic Gauss sums.     

High dimensional polynomial interpolation on sparse grids

We study polynomial interpolation on a d-dimensional cube, where d is large. We suggest to use the least solution at sparse grids with the extrema of the Chebyshev polynomials. The polynomial exactness of this method is almost optimal. Our error bounds show that the method is universal, i.e., almost optimal for many different function spaces. We report on numerical experiments for d = 10 using up to 652 065 interpolation points. This revised version was published online in June 2006 with corrections to the Cover Date.     

A fractional‐order Jacobi Tau method for a class of time‐fractional PDEs with variable coefficients

This paper presents a shifted fractional‐order Jacobi orthogonal function (SFJF) based on the definition of the classical Jacobi polynomial. A new fractional integral operational matrix of the SFJF is presented and derived. We propose the spectral Tau method, in conjunction with the operational matrices of the Riemann–Liouville fractional integral for SFJF and derivative for Jacobi polynomial, to solve a class of time‐fractional partial differential equations with variable coefficients. In this algorithm, the approximate solution is expanded by means of both SFJFs for temporal discretization and Jacobi polynomials for spatial discretization. The proposed tau scheme, both in temporal and spatial discretizations, successfully reduced such problem into a system of algebraic equations, which is far easier to be solved. Numerical results are provided to demonstrate the high accuracy and superiority of the proposed algorithm over existing ones. Copyright © 2015 John Wiley & Sons, Ltd.     

On perfect hashing of numbers with sparse digit representation via multiplication by a constant

Consider the set of vectors over a field having non-zero coefficients only in a fixed sparse set and multiplication defined by convolution, or the set of integers having non-zero digits (in some base b) in a fixed sparse set. We show the existence of an optimal (or almost-optimal, in the latter case) ‘magic’ multiplier constant that provides a perfect hash function which transfers the information from the given sparse coefficients into consecutive digits. Studying the convolution case we also obtain a result of non-degeneracy for Schur functions as polynomials in the elementary symmetric functions in positive characteristic.     

Polynomial algorithms for LP over a subring of the algebraic integers with applications to LP with circulant matrices

We show that a modified variant of the interior point method can solve linear programs (LPs) whose coefficients are real numbers from a subring of the algebraic integers. By defining the encoding size of such numbers to be the bit size of the integers that represent them in the subring, we prove the modified algorithm runs in time polynomial in the encoding size of the input coefficients, the dimension of the problem, and the order of the subring. We then extend the Tardos scheme to our case, obtaining a running time which is independent of the objective and right-hand side data. As a consequence of these results, we are able to show that LPs with real circulant coefficient matrices can be solved in strongly polynomial time. Finally, we show how the algorithm can be applied to LPs whose coefficients belong to the extension of the integers by a fixed set of square roots.     

Dependence of polynomial chaos on random types of forces of KdV equations

In this study, one-dimensional stochastic Korteweg–de Vries equation with uncertainty in its forcing term is considered. Extending the Wiener chaos expansion, a numerical algorithm based on orthonormal polynomials from the Askey scheme is derived. Then dependence of polynomial chaos on the distribution type of the random forcing term is inspected. It is numerically shown that when Hermite (Laguerre or Jacobi) polynomial chaos is chosen as a basis in the Gaussian (Gamma or Beta, respectively) random space for uncertainty, the solution to the KdV equation converges exponentially. If a proper polynomial chaos is not used, however, the solution converges with slower rate.     

Computational Complexity over thep-adic Numbers

A model of computation over thep-adic numbers, for odd primesp, is defined following the approach of Blum, Shub, and Smale. This model employs branching on the property of being a square inQ_pand unit height. The feasibility of systems of quadratic polynomials is shown to be NP-complete in this model. A polynomial time algorithm is given for feasibility of a single quadratic polynomial overQ_p.     

Polynomials defining many units

We classify the polynomials with integral coefficients that, when evaluated on a group element of finite order n, define a unit in the integral group ring for infinitely many positive integers n. We show that this happens if and only if the polynomial defines generic units in the sense of Marciniak and Sehgal. We also classify the polynomials with integral coefficients which provides units when evaluated on n-roots of a fixed integer a for infinitely many positive integers n.     

Sparse bivariate polynomial factorization

Motivated by Sasaki’s work on the extended Hensel construction for solving multivariate algebraic equations, we present a generalized Hensel lifting, which takes advantage of sparsity, for factoring bivariate polynomial over the rational number field. Another feature of the factorization algorithm presented in this article is a new recombination method, which can solve the extraneous factor problem before lifting based on numerical linear algebra. Both theoretical analysis and experimental data show that the algorithm is efficient, especially for sparse bivariate polynomials.     

Two-weight Hilbert transform and Lipschitz property of Jacobi matrices associated to hyperbolic polynomials

We are going to prove a Lipschitz property of Jacobi matrices built by orthogonalizing polynomials with respect to measures in the orbit of classical Perron-Frobenius-Ruelle operators associated to hyperbolic polynomial dynamics. This Lipschitz estimate will not depend on the dimension of the Jacobi matrix. It is obtained using some sufficient conditions for two-weight boundedness of the Hilbert transform. It has been proved in [F. Peherstorfer, A. Volberg, P. Yuditskii, Limit periodic Jacobi matrices with prescribed p-adic hull and a singular continuous spectrum, Math. Res. Lett. 13 (2-3) (2006) 215-230] for all polynomials with sufficiently big hyperbolicity and in the most symmetric case t=0 that the Lipschitz estimate becomes exponentially better when the dimension of the Jacobi matrix grows. This allows us to get for such polynomials the solution of a problem of Bellissard, in other words, to prove the limit periodicity of the limit Jacobi matrix. We suggest a scheme how to approach Bellissard's problem for all hyperbolic dynamics by uniting the methods of the present paper and those of [F. Peherstorfer, A. Volberg, P. Yuditskii, Limit periodic Jacobi matrices with prescribed p-adic hull and a singular continuous spectrum, Math. Res. Lett. 13 (2-3) (2006) 215-230]. On the other hand, the nearness of Jacobi matrices under consideration in operator norm implies a certain nearness of their canonical spectral measures. One can notice that this last claim just gives us the classical commutative Perron-Frobenius-Ruelle theorem (it is concerned exactly with the nearness of such measures). In particular, in many situations we can see that the classical Perron-Frobenius-Ruelle theorem is a corollary of a certain non-commutative observation concerning the quantitative nearness of pertinent Jacobi matrices in operator norm.     

A Unified Construction of Generalized Classical Polynomials Associated with Operators of Calogero–Sutherland Type

In this paper we consider a large class of many-variable polynomials which contains generalizations of the classical Hermite, Laguerre, Jacobi and Bessel polynomials as special cases, and which occur as the polynomial part in the eigenfunctions of Calogero–Sutherland type operators and their deformations recently found and studied by Chalykh, Feigin, Sergeev, and Veselov. We present a unified and explicit construction of all these polynomials.     

Sparse squares of polynomials

We answer a question left open in an article of Coppersmith and Davenport which proved the existence of polynomials whose powers are sparse, and in particular polynomials whose squares are sparse (i.e., the square has fewer terms than the original polynomial). They exhibit some polynomials of degree having sparse squares, and ask whether there are any lower degree complete polynomials with this property. We answer their question negatively by reporting that no polynomial of degree less than has a sparse square, and explain how the substantial computation was effected using the system CoCoA.

     

The bilateral birth–death chain generated by the associated Jacobi polynomials

We give a probabilistic interpretation of the associated Jacobi polynomials, which can be constructed from the three-term recurrence relation for the classical Jacobi polynomials by shifting the integer index n by a real number t. Under certain restrictions, this will give rise to a doubly infinite tridiagonal stochastic matrix, which can be interpreted as the one-step transition probability matrix of a discrete-time bilateral birth–death chain with state space on $\mathbb{Z}$. We also study the unique UL and LU stochastic factorizations of the transition probability matrix, as well as the discrete Darboux transformations and corresponding spectral matrices. Finally, we use all these results to provide an urn model on the integers for the associated Jacobi polynomials.     

Newton–Hensel Interpolation Lifting

The main result of this paper is a new version of Newton-Hensel lifting that relates to interpolation questions. It allows one to lift polynomials in ℤ[x] from information modulo a prime number p ≠ 2 to a power p^k for any k, and its originality is that it is a mixed version that not only lifts the coefficients of the polynomial but also its exponents. We show that this result corresponds exactly to a Newton--Hensel lifting of a system of 2t generalized equations in 2t unknowns in the ring of p-adic integers ℤ_p. Finally, we apply our results to sparse polynomial interpolation in ℤ[x].     

On a problem of Diophantus for rationals

Let q be a nonzero rational number. We investigate for which q there are infinitely many sets consisting of five nonzero rational numbers such that the product of any two of them plus q is a square of a rational number. We show that there are infinitely many square-free such q and on assuming the Parity Conjecture for the twists of an explicitly given elliptic curve we derive that the density of such q is at least one half. For the proof we consider a related question for polynomials with integral coefficients. We prove that, up to certain admissible transformations, there is precisely one set of non-constant linear polynomials such that the product of any two of them except one combination, plus a given linear polynomial is a perfect square.     

一类半正定多项式的配平方和算法

以牛顿多胞型技术为基础,根据牛顿多胞型中的点与点之间的相关性,给出了直接搜索多项式配平方和所需的最基本的项集Xs的算法,利用精确的符号算法PCAD,可将一类半正定多项式配成平方和,并编写了Maple程序"ASSOS",实现了多项式配平方和的自动生成.由多项式结构的稀疏性,此算法更能有效处理稀疏多项式.这一算法提高了多项式配平方和的效率,从而促进了一类代数不等式可读性证明的自动生成.除此之外,还给出了多项式不能表示为平方和的一个充分条件.     

Efficient parallel solution to large‐size sparse eigenproblems with block FSAI preconditioning

The choice of the preconditioner is a key factor to accelerate the convergence of eigensolvers for large‐size sparse eigenproblems. Although incomplete factorizations with partial fill‐in prove generally effective in sequential computations, the efficient preconditioning of parallel eigensolvers is still an open issue. The present paper describes the use of block factorized sparse approximate inverse (BFSAI) preconditioning for the parallel solution of large‐size symmetric positive definite eigenproblems with both a simultaneous Rayleigh quotient minimization and the Jacobi–Davidson algorithm. BFSAI coupled with a block diagonal incomplete decomposition proves a robust and efficient parallel preconditioner in a number of test cases arising from the finite element discretization of 3D fluid‐dynamical and mechanical engineering applications, outperforming FSAI even by a factor of 8 and exhibiting a satisfactory scalability. Copyright © 2011 John Wiley & Sons, Ltd.     

On testing the divisibility of lacunary polynomials by cyclotomic polynomials

An algorithm is described that determines whether a given polynomial with integer coefficients has a cyclotomic factor. The algorithm is intended to be used for sparse polynomials given as a sequence of coefficient-exponent pairs. A running analysis shows that, for a fixed number of nonzero terms, the algorithm runs in polynomial time.