Optimisation quadratique en variables binaires : quelques résultats et techniques

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

Polynomial identities for the ternary cyclic sum

We simplify the results of Bremner and Hentzel [J. Algebra 231 (2000) 387-405] on polynomial identities of degree 9 in two variables satisfied by the ternary cyclic sum [a, b, c] abc + bca + cab in every totally associative ternary algebra. We also obtain new identities of degree 9 in three variables which do not follow from the identities in two variables. Our results depend on (i) the LLL algorithm for lattice basis reduction, and (ii) linearization operators in the group algebra of the symmetric group which permit efficient computation of the representation matrices for a non-linear identity. Our computational methods can be applied to polynomial identities for other algebraic structures.

Model-order selection in Zernike polynomial expansion of corneal surfaces using the efficient detection criterion

Corneal-height data are typically measured with videokeratoscopes and modeled using a set of orthogonal Zernike polynomials. We address the estimation of the number of Zernike polynomials, which is formalized as a model-order selection problem in linear regression. Classical information-theoretic criteria tend to overestimate the corneal surface due to the weakness of their penalty functions, while bootstrap-based techniques tend to underestimate the surface or require extensive processing. In this paper, we propose to use the efficient detection criterion (EDC), which has the same general form of information-theoretic-based criteria, as an alternative to estimating the optimal number of Zernike polynomials. We first show, via simulations, that the EDC outperforms a large number of information-theoretic criteria and resampling-based techniques. We then illustrate that using the EDC for real corneas results in models that are in closer agreement with clinical expectations and provides means for distinguishing normal corneal surfaces from astigmatic and keratoconic surfaces.

Higher-Order spectra of nonlinear polynomial models for Chua's circuit

Polynomial models are shown to simulate accurately the quadratic and cubic nonlinear interactions (e.g. higher-order spectra) of time series of voltages measured in Chua's circuit. For circuit parameters resulting in a spiral attractor, bispectra and trispectra of the polynomial model are similar to those from the measured time series, suggesting that the individual interactions between triads and quartets of Fourier components that govern the process dynamics are modeled accurately. For parameters that produce the double-scroll attractor, both measured and modeled time series have small bispectra, but nonzero trispectra, consistent with higher-than-second order nonlinearities dominating the chaos.

Decomposition construction for secret sharing schemes with graph access structures in polynomial time

The purpose of this paper is to describe a new decomposition construction for perfect secret sharing schemes with graph access structures. The previous decomposition construction proposed by Stinson is a recursive method that uses small secret sharing schemes as building blocks in the construction of larger schemes. When the Stinson method is applied to the graph access structures, the number of such “small” schemes is typically exponential in the number of the participants, resulting in an exponential algorithm. Our method has the same flavor as the Stinson decomposition construction; however, the linear programming problem involved in the construction is formulated in such a way that the number of “small” schemes is polynomial in the size of the participants, which in turn gives rise to a polynomial time construction. We also show that if we apply the Stinson construction to the “small” schemes arising from our new construction, both have the same information rate.

An accuracy assessment of ASTER stereo images-derived digital elevation model by using rational polynomial coefficient model

The along-track stereo images of Advanced Spaceborne Thermal Emission and Reflection Radiometer (ASTER) sensor with 15 m resolution were used to generate Digital Elevation Model (DEM) on an area with low and near Mean Sea Level (MSL) elevation in Johor, Malaysia. The absolute DEM was generated by using the Rational Polynomial Coefficient (RPC) model which was run on ENVI 4.8 software. In order to generate the absolute DEM, 60 Ground Control Pointes (GCPs) with almost vertical accuracy less than 10 meter extracted from topographic map of the study area. The assessment was carried out on uncorrected and corrected DEM by utilizing dozens of Independent Check Points (ICPs). Consequently, the uncorrected DEM showed the RMSEz of ± 26.43 meter which was decreased to the RMSEz of ± 16.49 meter for the corrected DEM after post-processing. Overall, the corrected DEM of ASTER stereo images met the expectations.

Hybrid stiff-string-polynomial basis functions for vibration analysis of high speed rotating beams

A new finite element is developed for free vibration analysis of high speed rotating beams using basis functions which use a linear combination of the solution of the governing static differential equation of a stiff-string and a cubic polynomial. These new shape functions depend on rotation speed and element position along the beam and account for the centrifugal stiffening effect. The natural frequencies predicted by the proposed element are compared with an element with stiff-string, cubic polynomial and quintic polynomial shape functions. It is found that the new element exhibits superior convergence compared to the other basis functions.

Microprocessor-based polynomial generator

A new method of generating polynomials using microprocessors is proposed. The polynomial is generated as a 16-bit digital word. The algorithm for generating a variety of basic 'building block' functions and its implementation is discussed. A technique for generating a generalized polynomial based on the proposed algorithm is indicated. The performance of the proposed generator is evaluated using a commercially available microprocessor kit.

On the sufficient conditions for the equality of the unassignable polynomial and Davison's fixed polynomial of strongly connected systems

In this technical note, it is established that the unassignable polynomial defined for a not strongly connected decentralized control system is not equal to Davison's fixed polynomial. This leads to a "sufficient condition" for the equality of the unassignable polynomial and Davison's fixed polynomial for strongly connected systems.

A parallel wilf algorithm for complex zeros of a polynomial

A global recursive bisection algorithm is described for computing the complex zeros of a polynomial. It has complexityO(n 3 p) wheren is the degree of the polynomial andp the bit precision requirement. Ifn processors are available, it can be realized in parallel with complexityO(n 2 p); also it can be implemented using exact arithmetic. A combined Wilf-Hansen algorithm is suggested for reduction in complexity.