Absorbing sets of homogeneous subtractive algorithms

We consider homogeneous multidimensional continued fraction algorithms, in particular a family of maps which was introduced by F. Schweiger. We prove his conjecture regarding the existence of an absorbing set for those maps. We also establish that their renormalisations are nonergodic which disproves another conjecture due to Schweiger. Other homogeneous algorithms are also analysed including ones which are ergodic.     

Gcd of multivariate polynomials via Newton polytopes

We study geometric criteria to determine coprimality between multivariate polynomials. Our main contribution is the development of a polynomial-time algorithm (on the number of monomials) that detects coprimality of multivariate polynomials using Newton polytopes. We also show how to construct the gcd of two bivariate polynomials using their Newton polygons.     

The attractive Coulomb potential polynomials

TheJ matrix method in quantum mechanics developed by Heller, Reinhardt, and Yamani points to a set of orthogonal polynomials having a nonempty continuous spectrum in addition to an infinite discrete spectrum. Asymptotic methods are used to investigate the spectral properties of these polynomials. We also obtain generating functions for both numerator and denominator polynomials. The corresponding continued fraction is computed and the Stieltjes inversion formula is used to determine the distribution function.     

Comparison of time and spatial collocation methods for the heat equation

We combine a high-order compact finite difference scheme to approximate the spatial derivatives and collocation techniques for the time component to numerically solve the two-dimensional heat equation. We use two approaches to implement the time collocation methods. The first one is based on an explicit computation of the coefficients of polynomials and the second one relies on differential quadratures. We also implement a spatial collocation method where differential quadratures are utilized for spatial derivatives and an implicit scheme for marching in time. We compare all the three techniques by studying their merits and analyzing their numerical performance. Our experiments show that all of them achieve high-accurate approximate solution but the time collocation method with differential quadrature offers (with respect to the one with explicit polynomials) less computational complexity and a better efficiency. All our computations, based on parallel algorithms, are carried out on the CRAY SV1.     

Continued Fractions for Rogers–Szegö Polynomials

We evaluate different Hankel determinants of Rogers–Szegö polynomials, and deduce from it continued fraction expansions for the generating function of RS polynomials. We also give an explicit expression of the orthogonal polynomials associated to moments equal to RS polynomials, and a decomposition of the Hankel form with RS polynomials as coefficients.     

A new method for computing polynomial greates common divisors and polynomial remainder sequences

Summary A new method is presented for the computation of a greatest common divisor (gcd) of two polynomials, along with their polynomial remainder sequence (prs). This method is based on our generalization of a theorem by Van Vleck [12] and uniformly treats both normal and abnormal prs's, making use of Bareiss's [3] integer-preserving transformation algorithm for Gaussian elimination. Moreover, for the polynomials of the prs's, this method provides the smallest coefficients that can be expected without coefficient ged computations (as in Bareiss [3]) and it clearly demonstrates the divisibility properties; hence, it combines the best of both the reduced and the subresultant prs algorithms.This paper is affectionately dedicated to the memory of my father     

Degree distribution of the greatest common divisor of polynomials over 𝔽q

We study the degree distribution of the greatest common divisor of two or more random polynomials over a finite field ??_q. We provide estimates for several parameters like number of distinct common irreducible factors, number of irreducible factors counting repetitions, and total degree of the gcd of two or more polynomials. We show that the limiting distribution of a random variable counting the total degree of the gcd is geometric and that the distributions of random variables counting the number of common factors (with and without repetitions) are very close to Poisson distributions when q is large. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Determinant Forms for Extended Heat Functions and Expansions of Solutions of Associated Cauchy Problems

We briefly review series solutions of differential equations problems of the second order that lead to coefficients expressed in terms of determinants. Derivative type formulas involving a generating function with several parameters are developed for these determinant coefficients in first order problems. These permit constructing determinant forms for the heat polynomials and their Appell transforms. Hadamard's theorem for bounding determinants and conical regions are used to deduce simplified versions of expansion theorems involving these polynomials and associated Appell transforms. Extended versions of the heat equation are also considered.     

Non-symmetric Cauchy kernels for the classical groups

We give non-symmetric versions of the Cauchy kernel and Littlewood's kernels, corresponding to the types A, B, C and D, of the classical groups. Defining two families of key polynomials (one of them being the Demazure characters), we show that these new kernels are diagonal in the basis of key polynomials. We define scalar products such that the two families of key polynomials are adjoint to each other.     

On the degree elevation of Bernstein polynomial representation

The polynomials determined in the Bernstein (Bézier) basis enjoy considerable popularity in computer-aided design (CAD) applications. The common situation in these applications is, that polynomials given in the basis of degree n have to be represented in the basis of higher degree. The corresponding transformation algorithms are called algorithms for degree elevation of Bernstein polynomial representations. These algorithms are only then of practical importance if they do not require the ill-conditioned conversion between the Bernstein and the power basis. We discuss all the algorithms of this kind known in the literature and compare them to the new ones we establish. Some among the latter are better conditioned and not more expensive than the currently used ones. All these algorithms can be applied componentwise to vector-valued polynomial Bézier representations of curves or surfaces.     

Flat Power Series over a Finite Field

We define and describe a class of algebraic continued fractions for power series over a finite field. These continued fraction expansions, for which all the partial quotients are polynomials of degree one, have a regular pattern induced by the Frobenius homomorphism.This is an extension, in the case of positive characteristic, of purely periodic expansions corresponding to quadratic power series.     

Tensored polynomial models

The theme of the present paper is to introduce and study two different versions of tensor products of functional models, one over the underlying field and the other over the corresponding algebra of polynomials, as well as related models based on the Kronecker product of polynomial matrices. In the process, we study the Sylvester equation and its reduction to a polynomial matrix equation. We analyse the relation between the two tensor products and use this to elucidate the role of the Anderson-Jury generalized Bezoutians in this context.     

Computational acceleration of projection algorithms for the linear best approximation problem

This is an experimental computational account of projection algorithms for the linear best approximation problem. We focus on the sequential and simultaneous versions of Dykstra’s algorithm and the Halpern-Lions-Wittmann-Bauschke algorithm for the best approximation problem from a point to the intersection of closed convex sets in the Euclidean space. These algorithms employ different iterative approaches to reach the same goal but no mathematical connection has yet been found between their algorithmic schemes. We compare these algorithms on linear best approximation test problems that we generate so that the solution will be known a priori and enable us to assess the relative computational merits of these algorithms. For the simultaneous versions we present a new component-averaging variant that substantially accelerates their initial behavior for sparse systems.     

Two-dimensional orthogonal polynomials,their associated sets and the co-recursive sets

This paper deals with the general theory of sets of polynomials verifying a (d+1)-order recurrence. The cased=2 is specially carried out. First, we introduce the notion of associated set of a set of monic polynomials. A general formula for successive associated polynomials is given. The co-recursive sets of a two-dimensional orthogonal set are introduced. We calculate the corresponding formal Stieltjes functions.Finally, we determine the self-associated two-dimensional orthogonal sets and we show they are classical two-dimensional orthogonal sets, that is to say, their set of derivatives is also a two-dimensional orthogonal set.     

An application of Newton–Puiseux charts to the Jacobian problem

We study 2-dimensional Jacobian maps using so-called Newton–Puiseux charts. These are multi-valued coordinates near divisors of resolutions of indeterminacies at infinity of the Jacobian map in the source space as well as in the target space. The map expressed in these charts takes a very simple form, which allows us to detect a series of new analytical and topological properties. We prove that the Jacobian Conjecture holds true for maps (f,g) whose topological degree is ≤5, for maps with gcd(degf,degg)≤16 and for maps with. gcd(degf,degg) equal to 2 times a prime.     

On integral points on degree four del Pezzo surfaces

We report on our investigations concerning algebraic and transcendental Brauer–Manin obstructions to integral points on complements of a hyperplane section in degree four del Pezzo surfaces. We discuss two concepts of an obstruction at an archimedean place. Concrete examples are given of pairs of non-homogeneous quadratic polynomials in four variables representing (0, 0) over Q and over Z _p for all primes p, but not over Z. By blow-up, these yield cubic polynomials in three variables all integral solutions of which satisfy a gcd condition.     

Numerical computation of characteristic polynomials of Boolean functions and its applications

We study the problem of evaluation of characteristic polynomials of Boolean functions with applications to combinational circuit verification. Two Boolean functions are equivalent if and only if their corresponding characteristic polynomials are identical. However, to verify the equivalence of two Boolean functions it is often impractical to construct the corresponding characteristic polynomials due to a possible exponential blow-up of the terms of the polynomials. Instead, we compare their values at a sample point without explicitly constructing the characteristic polynomials. Specifically, we sample uniformly at random in a unit cube and determine whether two characteristic polynomials are identical by their evaluations at the sample point; the error probability is zero when there are no round-off errors. In the presence of round-off errors, we sample on regular grids and analyze the error probability. We discuss in detail the Shannon expansion for characteristic polynomial evaluation. This revised version was published online in June 2006 with corrections to the Cover Date.     

Orlicz-Pettis Polynomials on Banach Spaces

 We introduce the class of Orlicz-Pettis polynomials between Banach spaces, defined by their action on weakly unconditionally Cauchy series. We give a number of equivalent definitions, examples and counterexamples which highlight the differences between these polynomials and the corresponding linear operators.     

Sequence of operations analysis for dynamic data structures

This paper introduces a rather general technique for computing the average-case performance of dynamic data structures, subjected to arbitrary sequences of insert, delete, and search operations. The method allows us effectively to evaluate the integrated cost of various interesting data structure implementations, for stacks, dictionaries, symbol tables, priority queues, and linear lists; it can thus be used as a basis for measuring the efficiency of each proposed implementation. For each data type, a specific continued fraction and a family of orthogonal polynomials are associated with sequences of operations: Tchebycheff for stacks, Laguerre for dictionaries, Charlier for symbol tables, Hermite for priority queues, and Meixner for linear lists. Our main result is an explicit expression, for each of the above data types, of the generating function for integrated costs, as a linear integral transform of the generating functions for individual operation costs. We use the result to compute explicitly integrated costs of various implementations of dictionaries and priority queues.     

Models for capacity and electricity market design

The paper employs Operations Research methods for analysis of electricity and capacity markets. We provide two algorithms that determine the optimal capacity structure with account of fixed and variable costs. The first one relates to the case where there are several capacity types, and for each type the capacity constraint is not binding. The second algorithm is applicable when electricity is produced by standard small generators with the same capacity and different costs. Then we study two typical architectures of the market and examine their Nash equilibria. We consider a uniform price supply function auction in the electricity market. For pay-as-bid and uniform price versions of the capacity market design, we compare the equilibrium outcomes with the optimal capacity structure. The paper shows that the market equilibrium corresponds to the optimal capacity structure under conditions of pure competition, full rationality, and completely informed agents in the market. However, under more realistic assumptions, selection of the optimal structure is unlikely. Finally we provide the auction design that realizes such selection of capacities and does not require any additional information of each producer besides his own production costs. We establish sufficient conditions for perfect competition in the market.