PROGRAM SUMMARY
Title of program:
LiftingFactorisation.nb 1.0
Catalogue identifier:
ADLE
Ref. in CPC:
127(2000)309
Distribution format: gzip file
Number of lines in distributed program, including test data, etc:
2163
Keywords:
General purpose, Other numerical, Computer algebra, Wavelets, lifting,
Euclidean algorithm, Laurent polynomials, Grobner bases,
Polynomial reduction.
Programming language used: Mathematica
Nature of physical problem:
Spectral analysis and compression of signals or images.
Method of solution
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].
Restrictions on the complexity of the problem
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 of the program
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.
References
[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