Review of Multidimensional Systems Theory, N.K.Bose, ed.

by Eduardo D. Sontag, Dept.of Mathematics, Rutgers University, New Brunswick, NJ 08903.

The Area
Few parts of application-oriented mathematics have benefited from the interaction with modern algebraic
and analytic geometry as much as the area usually refered to as multidimensional systems theory. This field
consists of the study of various topics in the theory of functions of several complex variables, motivated
mostly by problems in network design and synthesis and by signal processing applications. Because of finite
realizability constraints, the focous is often on rational functions; this accounts for the strong algebraic
flavor of papers in the area, and in particular the use of techniques and results from commutative algebra.
A linear-algebraic component is introduced by the need to consider matrices whose entries are analytic or
rational functions.
In classical systems and control theory, one studies ordinary differential equations
y (n) (t) + a1 y (n1) (t) + + an y(t) = b1 u(n1) (t) + + bn u(t),

(1)

where a1 , , an , b1 , , bn are fixed real numbers, and u(), y() are respectively the input and output signals.
The (scalar) independent variable t is interpreted as time. Multidimensional systems appear when dealing
instead with partial differential (or difference) equations. The independent variables may now represent
different space coordinates as in image processing applications, or perhaps mixed time and space variables
as in seismic data processing. Multidimensional models are also useful when studying certain types of
functional differential equations in one independent variable, as delay-differential systems.
Taking Laplace transforms in (1), we see that the input/output behavior of a classical system is characterized by the rational function
w(s) =

sn

b1 sn1 + + bn
.
+ a1 sn1 + + an

Questions of stability, in the sense that small input signals should produce small output signals, depend
basically on the location of the singularities of w(s). If we assume that the numerator and denominator of
w(s) are relatively prime, this means that stability is related to the location of the zeroes of
Q(s) = sn + a1 sn1 + + an .
For difference equations, which appear in digital signal processing applications, the situation is entirely analogous, except that z-transforms are used instead of Laplace transforms. When dealing with
multidimensional systems, Laplace or z-transforms result in rational functions in several variables. Even if
we write such a function as a quotient of two relatively prime polynomials, it is clear that the locus of zeroes
of the denominator is no longer sufficient to characterize singularities, since this locus may intersect the set
of zeroes of the numerator. Moreover, the study of zero sets themselves is now highly nontrivial indeed,
such a study is precisely the subject matter of algebraic geometry.
Another set of problems, motivated by realizability issues for systems and networks, involve problems of
factorization as well as various concepts of positivity of a rational function. Here again, the passage from
classical systems to the multidimensional case changes the difficulty of the study in an essential way.
Much of the work in multidimensional systems has dealt with the search of easily testable conditions
guaranteeing various types of stability and positiveness. In principle, most questions of this sort are decidable
in the sense of computer science, since they can be stated in terms of the first order theory of real closed
fields. Unfortunately, this fact turns out to be missleading, since the computational complexities involved are
worse than exponential. For instance, no simple tests are known for deciding if a polynomial Q(z1 , , zr )
has no zeroes in the closed polydisk
|z1 | 1, , |zr | 1,
1

in contrast to the classical case (Routh-Hurwitz type tests). A number of tests have been proposed; see for
instance [AJ], [B], and references there.
From the linear algebraists point of view, matters become interesting when multivariable systems are
considered. These are systems for which both inputs and outputs (u and y above) are vector-valued instead
of scalar. Here one has to study properties (factorizations, positivity, etc.) of polynomial and rational
matrices. A large amount of accumulated knowledge notwithstanding (see e.g. [MD]), linear algebra over
rings is still very much in its infancy, especially with regards to effective algorithms. For example, one basic
difficulty is that the rank is no longer a complete invariant for the size of minimal factorizations. If A(z) is
a matrix of polynomials (each entry is a polynomial in z1 , , zr ) of rank k, it is false in general that there
exist polynomial matrices B(z), C(z), with k columns and rows respectively, such that A(z) = B(z)C(z).
Such rank factorizations, which are central in system design, exist for all A and k if and only if r 2 (see
[DS]); in general one needs a larger intermediate dimension. (For networks as opposed to control systems,
factorization problems typically involve further positivity constraints.)

The book
The present book consists of a collection of articles by various authors. The editors goal, stated in
the introduction, was to provide an overview of some current research topics in multidimensional systems.
On that basis the book is quite successful. By and large the articles are very clearly written, and extensive
references are provided. The main criticism one could make is the lack of cross-referencing between articles.
Ideally the editor should have coordinated the contributions a bit. On the other hand, the first paper,
Trends in Multidimensional Systems Theory, by Bose himself, includes an overview of the rest, drawing
some connections. The article reviews the current (ca. 1984) status of various questions involving problems
of stability and/or factorization. The writing could benefit from some polishing, but it is informative. The
next article, also by the editor, consists basically of an annotated (and very useful) bibliography of papers
on Pade-type approximation in the multivariate (and even matrix) case.
The paper Causal and weakly causal 2-D filters with applications in stabilization, by J.P. Guiver and
Bose, begins by reviewing definitions of causality for 2-D (picture-processing) systems. The right definition of causality is not obvious in this context. For classical (1-D) systems, there is a natural such
notion: the future must not affect the past; for multidimensional systems, various definitions are possible,
depending on the goals of the study. Typically, one is interested in recursive implementations of filters,
and hence in causality with respect to a cone in <2 which plays the role of the past. Once causality has
been properly defined, and a notion of stability has been introduced, it is possible to study the question of
feedback stabilization of unstable systems. The authors present an excellent exposition of various results in
this area, using a coprime factorization approach. In the time-honored tradition of reviewers advertising,
Ill add the reference [KS] to those given in the paper. This reference clarifies the meaning of the various
stabilizability hypotheses in state-space terms.
Chapter 4, Stabilization of linear spatially-distributed continuous-time and discrete-time systems, by
E.W. Kamen, deals with systems for which input and output signals depend on both continuous and discrete
variables. This situation arises for instance when discretizing only one variable (the time) in a system
described by a p.d.e. with two independent variables. In such examples, it is often the case that there is
enough decay along the spatial (non-time) coordinate; one may then study this type of distributed system as
a system over a ring, meaning a control system analogous to those studied in the classical finite-dimensional
linear theory, but where the coefficient matrices have entries now over a ring of operators. Specifically, the
author studies state space systems corresponding to controlled differential equations in the Banach space
l (Z, <n ), where the right-hand side contains operators in l1 (Z, <n ). The exposition is clear, and includes
a careful review of reachability and stabilizability and local/global questions. It should be remarked that
Kamen was responsible, in the early 70s, for the development of the theory of systems over rings as applied
to distributed systems. His contributions dealing with delay systems are well-known, and relate naturally to
2

the material in this chapter. See the recent textbook [BBV] for an exposition of many aspects of the theory
of systems over rings as well as further references.
The next article is Linear shift-variant multidimensional systems, by H.M. Valenzuela and Bose. A shiftvariant filter is the multidimensional analogue of a time-varying linear system (the coefficients in equation
(1) are functions of time instead of constants). Such models appear when considering, for instance, blurring
due to lens aberration. To obtain a reconstruction of the original image, one needs to deconvolve, or more
precisely, to pass the observed picture through an inverse system. The authors develop the basic theory of
shift-variant systems in the state and input/output senses, and present results on system inversion. I found
the two examples, dealing with applications to image deconvolution, to be the most interesting part of the
paper.
The book turns more purely algebraic with the next article. Chapter 6 is entitled Gr
obner bases: an
algorithmic method in polynomial ideal theory, by B. Buchberger. Many, if not most, problems in multidimensional system theory require at some point or another the calculation of ideal (or module) bases. For
instance, solve a homogeneous system of linear equations over a polynomial ring means give a general solution, i.e., a basis of a suitable nullmodule. The method of Gr
obner bases, introduced by Buchberger about
20 years ago, has proved to be well-suited to computer implementation. As opposed to the older technique
of G. Hermann (ca. 1926), the Gr
obner-basis method has a computational complexity that depends on the
particular ideal being studied (instead of a fixed running time which depends of the number of variables
and the degrees of the polynomials appearing in the problem statement). Its worst-case complexity is still
double exponential in the number of variables, however, a fact that would not surprise anyone that has used
the corresponding MACSYMA package. (We have been told by Professor F. Mora that the next release of
REDUCE will incorporate a much-improved Gr
obner package, which should result in at least an order of
magnitude speed-up over the current MACSYMA version.) The article presents an excellent exposition of
the theory of Gr
obner bases, as well as the various heuristics that can be (and are) used to make it more
efficient. This is the best exposition on the topic that I have seen.
The book closes with a short article by J.P. Guiver on solvability conditions for linear equations over
a polynomial ring in two variables, and an article listing various open problems. This last article may be
useful to those contemplating starting research in the area.
On the whole, the book is worth looking at, providing a good introduction to current research in a very
active area of applied mathematics.
References.
[AJ] Anderson, B.D.O., and Jury, E.I., Stability of multidimensional recursive filters, IEEE Trans.
Circuits and Syst. (21) (1974): 300-304.
[B] Bose, N.K., Problems and progress in multidimensional systems theory, Proceedings IEEE (65)
(1976): 824-840.
[BBV] Brewer,J.W., John W.Bunce, and F.S.Van Vleck, Linear Systems over Commutative Rings,
Marcel Dekker, NY, 1986.
[DS] Dicks,W. and E.D.Sontag, Sylvester domains, J.Pure Appl. Algebra (13) (1978):243-275.
[KS] Khargonekar,P.P. and E.D.Sontag, On the relation between stable matrix fraction decompositions
and regulable realizations of systems over rings, IEEE Trans.Autom. Control (27) (1982):627-638.
[MD] McDonald, Bernard R., Linear Algebra over Commutative Rings, Dekker, New York, 1984.