Elsevier Science Home
Computer Physics Communications Program Library
Full text online from Science Direct
Programs in Physics & Physical Chemistry
CPC Home

[Licence| Download | New Version Template] adle_v1_0.gz(13 Kbytes)
Manuscript Title: Automation of the lifting factorisation of wavelet transforms.
Authors: M. Maslen, P. Abbott
Program title: LiftingFactorisation.nb 1.0
Catalogue identifier: ADLE_v1_0
Distribution format: gz
Journal reference: Comput. Phys. Commun. 127(2000)309
Programming language: Mathematica.
Keywords: General purpose, Other numerical, Computer algebra, Wavelets, Lifting, Euclidean algorithm, Laurent polynomials, Grobner bases, Polynomial reduction.
Classification: 4.12, 5.

Nature of problem:
Spectral analysis and compression of signals or images.

Solution method:
Symbolic computer algebra is used to automate the Euclidean algorithm for Laurent polynomials [1] so as to factorise wavelet transforms yielding a sequence of simple arithmetic operations suitable for parallel, in-place, implementation [2].

The program requires that the Laurent polynomial quotients used in the algorithm have Laurent degree at most 1. The polyphase matrix must have unit determinant (though any polyphase matrix may be adjusted to satisfy this criterion [2]).

Unusual features:
The program can find symbolic greatest common divisors (gcds) of two Laurent polynomials. Using Grbner bases and polynomial reduction on the filter coefficients reduces the number of unknown coefficients appearing in expressions. There is also capability to convert the lifting steps from mathematical notation to computer pseudo-code, suitable for implementation in C or Fortran.

[1] M.J. Maslen, Factoring Wavelet Transforms into Lifting Steps, (University of Western Australia, 1997). URL: http://www.physics.uwa.edu.au/~paul/publications.html
[2] I. Daubechies, W. Sweldens, J. Fourier Anal. Appl. 4 (1998) 247. URL: http://cm.bell-labs.com/who/wim/papers/papers.html#factor