Subdivisions, Multiresolution, Biorthogonal Matrices with Application to Image Compression and Reconstruction
Richard Bartels · Retired Professor, University of Waterloo
Abstract: Multiresolutions based upon wavelets are currently used for image compression. In this talk we outline a construction process for multiresolutions that begins with subdivisions for meshes of geometric points and uses a local least-squares approximation approach to generate finite decomposition and reconstruction filters. The construction ignores underlying function spaces and proceeds entirely via linear algebra to set up and solve a biorthogonal equation system of four matrices whose generic rows and columns provide the filters. The construction is easy to describe, can be carried out readily with the aid of a symbolic algebra system such as Maple, and has shown preliminary promise at being effective in image compression. The construction can be extended easily to mesh topologies other than tensor products, and it can also handle boundaries. In this talk we shall outline the construction, compare and contrast it with wavelet-based multiresolution, and give some preliminary examples of results on images.
This is joint work with Faramarz Samavati of the University of Calgary.
Computing the fundamental units and regulators of a cubic function field
Yoonjin Lee · Simon Fraser University
Abstract: We present algorithms for computing the two fundamental units and the regulator of a cyclic cubic extension of a rational function field over a field of order q congruent to 1 mod 3. The procedure is based on a method originally due to Voronoi that was recently adapted to purely cubic function fields of unit rank one. Our numerical examples show that the two fundamental units tend to have large degree, and frequently, the extension has a very small ideal class number.
Probabilistic Algorithms for the Stable Interpolation of Sparse Approximate Polynomials
Mark Giesbrecht · Symbolic Computation Group, University of Waterloo
Abstract: Interpolation of polynomials is a fundamentally important problem in both numerical and algebraic computing, and has been very well studied for its mathematical properties. The usual (dense) representation of multivariate polynomials can get very large, even at relatively low degrees, when the number of variables is modest. Exploiting sparsity is a key to computing efficiently with them. Hence, we consider the problem of sparse interpolation of approximate multivariate polynomials. We work in the "black box" model, where we can evaluate the polynomial at any point, but have no information on how the values are computed or obtained. Both the inputs and outputs of the black-box polynomial will be assumed to have some error, and all numbers are represented in standard, fixed-precision, floating point arithmetic. We present a "probabilistically stable" algorithm which gives a numerically reliable solution with high probability. We also note (and use) the strong similarity between the exact Ben-Or & Tiwari (1988) sparse interpolation algorithm and the classical Prony's (1795) method for interpolating a sum of exponential functions, and exploit the generalized eigenvalue reformulation of Prony's method. We look at the numerical stability of our algorithms and the sensitivity of the solutions, as well as the expected numerical conditioning achieved through randomization. This is joint work with Wen-shin Lee and George Labahn.
Spectral Properties of Boolean Functions and their Crypto and Quantum Context
Matthew G. Parker · Selmer Centre, Universitetet i Bergen
Abstract: Classical cryptosystems can be attacked via linear and/or differential approximations and, these days, such systems are designed to be resistant to such attacks. We will discuss possible ways round this. The idea is to view the cryptosystem as a quantum system. This reveals new types of approximation in the context of Hilbert space. This is a win-win situation. Either one can break the cryptosystem and achieve instant fame or, more likely, identify certain well-designed crypto-primitives as superior (but somewhat impractical) entangling primitives of qubit systems.