Algorithmic aspects of algebraic system theory [Elektronische Ressource] / vorgelegt von Kristina Schindelar

Sujets

• Mathematics

Informations

• Publié par: rheinisch-westfalischen_technischen_hochschule_-rwth-_aachen
• Publié le: 01 janvier 2010
• Nombre de lectures: 22
• Langue: English

Extrait

Algorithmic aspects of algebraic
system theory
Von der Fakult¨at fur¨ Mathematik, Informatik und
Naturwissenschaften der RWTH Aachen University zur Erlangung des
akademischen Grades einer Doktorin der Naturwissenschaften
genehmigte Dissertation vorgelegt von
Diplom-Mathematikerin
Kristina Schindelar
aus Bratislava
Berichter: Universit¨atsprofessorin Dr. Eva Zerz
Universit¨atsprofessor Dr. Sebastian Walcher
Tag der mundlic¨ hen Prufung¨ : 16. M¨arz 2010
Diese Dissertation ist auf den Internetseiten der Hochschulbibliothek online
verfug¨ bar.Contents
Preface 5
1 Introduction to algebraic system theory 9
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2 Basic properties of linear systems . . . . . . . . . . . . . . . . . . . . . 10
1.3 One-dimensional systems over rings . . . . . . . . . . . . . . . . . . . . 19
1.4 time-varying systems . . . . . . . . . . . . . . . . . . 24
1.5 Multi-dimensional time-varying systems. . . . . . . . . . . . . . . . . . 31
1.6 Most powerful unfalsified model . . . . . . . . . . . . . . . . . . . . . . 34
2 Gr¨obner bases 41
2.1 Commutative Gr¨obner bases . . . . . . . . . . . . . . . . . . . . . . . . 42
2.1.1 One-dimensional case and applications to signals and systems . 47
2.2 Non-commutative Gr¨obner bases . . . . . . . . . . . . . . . . . . . . . 53
2.2.1 Algorithmic computations . . . . . . . . . . . . . . . . . . . . . 60
3 One-dimensional systems over finite rings 63
3.1 Preliminaries on p-generator sequences . . . . . . . . . . . . . . . . . . 66
3.2 Minimal Gr¨obner p-basis and the p-PLM property . . . . . . . . . . . . 69
3.3 Application to signals and systems . . . . . . . . . . . . . . . . . . . . 76
4 One-dimensional time-varying systems 79
4.1 Decoupling systems over Ore extensions. . . . . . . . . . . . . . . . . . 80
4.1.1 Polynomial decoupling . . . . . . . . . . . . . . . . . . . . . . . 86
4.2 Normal forms for time-varying systems . . . . . . . . . . . . . . . . . . 92
4.2.1 Examples, Applications and Comparison . . . . . . . . . . . . . 97
5 Multi-dimensional time-varying systems 103
5.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
5.2 Application to linear exact modeling . . . . . . . . . . . . . . . . . . . 108
5.2.1 VMPUM using the Weyl algebra . . . . . . . . . . . . . . . . . 112
5.2.2 VMPUM using the difference algebra . . . . . . . . . . . . . . . 118
Conclusion and future work 123
Bibliography 125
34 CONTENTSPreface
The mathematical roots of system and control theory date back to the paper “On
Governors” by J. C. Maxwell published 1868 in Proceedings of the Royal Society of
London. TheseminalworkofR.E.Kalmanestablishedsystemtheoryasamathemat-
ical discipline in the 1950s. About thirty years later, J. C. Willems proposed a novel
approach to signals and systems, the so-called behavioral approach. This approach
offers a very general definition of a dynamical system, a triple consisting of the math-
ematical model of time, the system-relevant quantities summarized in the so-called
signals, andasystemlaw, thatis, equationsdefiningtherelationsbetweenthesignals.
The contribution of U. Oberst, which appeared in 1990, gives fundamental insight for
algebraic system theory. A very important algebraic property of the signal space is
realized to be highly copious for signals and systems there, namely the property of the
signal space to be an injective cogenerator over the underlying operator ring. The al-
gebraicapproachtosystemtheoryhasbeendevelopedamongothersbyB.Malgrange,
U. Oberst, J. F. Pommaret, A. Quadrat and E. Zerz.
Thegoalofalgebraicsystemtheoryisthestructuralanalysisofdynamicalsystemsus-
ingalgebraictools. Thesesystemsmayarisefromvariouspracticalproblemssettledfor
instanceinascientific,technicaloreconomicalarea. Thesystemsaremainlydescribed
via differential or difference equations. Their solutions are contained in a certain sig-
nal space which possesses a module structure over the ring of differential/difference
operators. In case the signal space is an injective cogenerator, algebraic properties
of the system module are dual to analytic properties of the signals due to Oberst’s
observation. Then control theoretic characterizations like autonomy, controllability
and observability can be translated into algebraic terms.
Classically linear time-invariant systems with field coefficients are studied. In the re-
cent past variations of these systems have proved to be worthy for extended studies.
From the applied point of view, there is obviously the interest to consider correspond-
inggeneralizations. Fromthealgebraicpointofview,someparticularsettingsarevery
interestingforfurtherinvestigationssinceringtheoryandhomologicalalgebraprovide
adeepinsight. Beyondtheoreticalstudies, thecomputeralgebramachineryallowsthe
enormous benefit of constructive analyses. This thesis elaborates both aspects, the
theoretical and the computational, in parallel. It is organized as follows.
Chapter 1 and Chapter 2 serve for an extended introduction. System theoretical
aspects are provided in Chapter 1. Basic concepts and definitions are presented and
furthermore the following chapters are motivated from the system theoretical point of
view. Section 1.3 motivates the subject of study of Chapter 3, Section 1.4 points out
the relevance of Chapter 4 and finally Section 1.5 and Section 1.6 give an introduction
56 CONTENTS
toChapter5. Chapter2isdevotedtoGr¨obnerbasestheory. Besidetheclassicalcaseof
polynomial modules with field coefficients, we discuss ring coefficients andG-algebras.
Connections between G-algebras and Ore algebras are outlined. Furthermore their
relevance for system theory is shown and the algorithmic motivation for the following
Chapters is composed.er 3 studies systems with coefficients in a finite ring, in contrast to the classical
case. The general motivation for this framework stems mainly from communication
theory. However, the extension leads to problems like zero-divisors and the principal
ideal domain property is lost. Therefore concepts useful for coding fail to generalize
straightforwardly. In the field case the so-called predictable degree property is useful
for many areas of system theory, ranging from controller parameterization to minimal
realizations of linear systems over fields. This property does not carry over directly to
the ring case. The paper “The predictable degree property and row reducedness for
systems over a finite ring” by M. Kuijper, R. Pinto, J. W. Polderman and P. Rocha
[KPP07]establishesanewframeworkwhichallowstheadoptionofthatclassicalresult
inanovelsetting. ResultsofthatworkwerepresentedintheplenarytalkofM.Kuijper
at the international symposium “Mathematical Theory of Networks and Systems” in
2008. Thereupon J. Rosenthal proposed the conjecture that the presented results are
closelyconnectedtothe topicofGrobner¨ bases. Thishasprovedtobecorrect. Bythe
toolofGr¨obnerbasestheresultsof[KPP07]areextendedtoamoregeneralframework
which additionally allows concrete calculations. For this purpose the notion of the so-
called minimal Gr¨obner p-basis is established and the connection to known results
is pointed out. The application to parametrization of all shortest linear recurrence
relations and to minimal state realization are discussed. The results presented in
Chapter 3 are based on joint work with M. Kuijper.er 4 is focused on one-dimensional systems with time-varying rational coeffi-
cients. This leads to the non-commutative operator ring called rational Weyl algebra
which is a principal ideal domain. Therefore the non-commutative analogon to the
Smith form, the so-called Jacobson form, exists. This normal form can be used to
obtain a decomposition into a controllable and an autonomous subsystem of the cor-
responding linear abstract system. Furthermore the order of the underlying ordinary
differential equation system is obtained directly. But computational problems known
from the commutative counterpart even increase due to the non-commutative struc-
ture, namely the explosive growth of the coefficients. A novel approach which can
be applied in a completely fraction free framework is presented in this chapter. This
approach shows first how to obtain a decoupled form. It should be stressed that this
decoupled form may even be interesting by itself. Further we show how to obtain a
normal form from the decoupled form. Due to collaboration with V. Levandovskyy
the proposed algorithm can even be applied to an extended operator class of certain
G-algebras. The implementation is realized as a library called jacobson.lib for the
computer algebra system Singular::Plural [GPS05, GLH05], which is freely avail-
able. This implementation is compared with all implementations which are available
to the best of our knowledge.
In [AW93] a behavioral approach to linear exact modeling is formulated for one-
dimensional systems with constant coefficients. This problem of system identification
is extended to a multi-dimensional setting in [Zer05, Zer08]. In co-operation with
V. Levandovskyy and E. Zerz, this modeling concept is developed for polynomial-CONTENTS 7
exponential signals in a multi-dimensional time-varying model class in Chapter 5.
These model classes are summarized in the so-called Ore algebras. The ide