Groebner Bases in Multidimensional Systems and Signal Processing

Open Access
Charoenlarpnopparut, Chalie
Graduate Program:
Electrical Engineering
Doctor of Education
Document Type:
Date of Defense:
November 30, 1999
Committee Members:
  • Mario Sznaier, Committee Member
  • Robert E Van Dyck, Committee Member
  • Kenneth Jenkins, Committee Member
  • Frank Richard Deutsch, Committee Member
  • John Metzner, Committee Member
  • Nirmal K Bose, Committee Chair
  • unimodular
  • primeness
  • minimax controller
  • filter bank
  • mulivariate matrix fractorization
  • Groebner Bases
The theory of Groebner bases for ideals and modules over a multivariate polynomial ring is applied to solve several problems of interest in multidimensional systems and signal processing. In 1979, Youla and Gnavi explained the implications of zero, minor and factor coprimeness in matrix-fraction descriptions of multivariate rational transfer matrices. In 1982, Guiver and Bose showed how primitive factorization of bivariate matrices can be implemented via computations only in the ground field, i.e., an extension field is not required. Since then several publications in the area emerged, including, most recently, the papers of Park-Kalker-Vetterli, Fornasini-Valcher, and Lin. The tests for multivariate polynomial matrix zero coprimeness and minor coprimeness are implemented algorithmically while progress towards the difficult problem of multivariate matrix factor extraction is also reported. The multivariate polynomial matrix factorization algorithm when some conditions are satisfied is developed. Some remarks and limitations of the algorithm are also reported. The multivariate polynomial matrix factorization algorithm developed is applied to the multidimensional filter bank design problem. This algorithm and another algorithm for computing a globally minimal generating matrix of the syzygy of solutions associated with a polynomial matrix are both associated with a zero coprimeness constraint that characterizes perfect reconstruction filter banks. Generalizations as well as limitations of recent results which incorporate the perfect reconstruction as well as the linear phase constraints are discussed with several examples and counterexamples. Specifically, a Groebner basis-based proof for perfect reconstruction with linear phase is given for the case of two-band multidimensional filter banks and the algorithm is illustrated by a nontrivial design example. This detailed design example and simulation results are based on an embedded zerotree wavelet encoding algorithm. Progress and bottlenecks in the multidimensional multiband case are also reported. The Groebner basis theory is then applied to the minimax controller design using rate feedback, which was initiated by Bucy-Namiri-Velman in 1990. The complete analytic characterization and solution construction for this problem is given when the plant consists of a known fixed set of coupled oscillators of cardinality three (or order six). The case when the plant order is eight is also considered based on the use of Groebner bases. The results are given in the compact triangular form of polynomial equations so that the numerical solutions are readily computed by simple recursive substitution of the values of variables, already computed. In general, the problem is analytically intractable and suboptimal solutions based on numerical techniques are then the only recourse.