Automation of the lifting factorisation of wavelet transforms. M. Maslen, P. Abbott.

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
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