A Computational Theory of Laurent Polynomial Rings and Multidimensional FIR Systems

H-J. Park

EECS Department
University of California, Berkeley
Technical Report No. UCB/ERL M95/39
May 1995

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1995/ERL-95-39.pdf

A Laurent polynomial ring is a natural ground ring for the study of FIR (Finite Impulse Response) systems in signal processing since an FIR filter bank can be seen as a matrix over this ring, and the notion of perfect reconstruction is represented by the unimodularity of the corresponding multivariate Laurent polynomial matrices. Contrary to the conventional affine approach to the theory of multidimensional FIR filter banks as a linear algebra over polynomial rings, the toric approach based on Laurent polynomial rings offers a more adequate framework. In connection with these applications, we look at the computational aspects of the theory of modules over Laurent polynomial rings, and develop a few of their applications to signal processing. A new, computationally effective algorithm for the Quillen-Suslin Theorem is found, and implemented using the computer algebra package SINGULAR. An algorithmic proof of Suslin's Stability Theorem is found, which gives an analogue of Gaussian Elimination over a polynomial ring. An algorithmic process of converting results over polynomial rings to their counterparts over Laurent polynomial rings is developed. With the help of this process, we extend the above two algorithms, the Quillen-Suslin Theorem and Suslin's Stability Theorem, to the case of Laurent polynomial rings. A notion of inner product spaces over Laurent polynomial rings is introduced, and a theoretical framework for this notion is developed. A few outstanding problems in multidimensional perfect reconstructing filter banks are shown to be solvable with the aid of the above algorithms. Explicit examples are included that are worked out by SINGULAR.

BibTeX citation:

@techreport{Park:M95/39,
    Author = {Park, H-J.},
    Title = {A Computational Theory of Laurent Polynomial Rings and Multidimensional FIR Systems},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1995},
    Month = {May},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1995/2775.html},
    Number = {UCB/ERL M95/39},
    Abstract = {A Laurent polynomial ring is a natural ground ring for the study of FIR (Finite Impulse Response) systems in signal processing since an FIR filter bank can be seen as a matrix over this ring, and the notion of perfect reconstruction is represented by the unimodularity of the corresponding multivariate Laurent polynomial matrices. Contrary to the conventional affine approach to the theory of multidimensional FIR filter banks as a linear algebra over polynomial rings, the toric approach based on Laurent polynomial rings offers a more adequate framework. In connection with these applications, we look at the computational aspects of the theory of modules over Laurent polynomial rings, and develop a few of their applications to signal processing. A new, computationally effective algorithm for the Quillen-Suslin Theorem is found, and implemented using the computer algebra package SINGULAR. An algorithmic proof of Suslin's Stability Theorem is found, which gives an analogue of Gaussian Elimination over a polynomial ring. An algorithmic process of converting results over polynomial rings to their counterparts over Laurent polynomial rings is developed. With the help of this process, we extend the above two algorithms, the Quillen-Suslin Theorem and Suslin's Stability Theorem, to the case of Laurent polynomial rings. A notion of inner product spaces over Laurent polynomial rings is introduced, and a theoretical framework for this notion is developed. A few outstanding problems in multidimensional perfect reconstructing filter banks are shown to be solvable with the aid of the above algorithms. Explicit examples are included that are worked out by SINGULAR.}
}

EndNote citation:

%0 Report
%A Park, H-J.
%T A Computational Theory of Laurent Polynomial Rings and Multidimensional FIR Systems
%I EECS Department, University of California, Berkeley
%D 1995
%@ UCB/ERL M95/39
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1995/2775.html
%F Park:M95/39