|
||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||
 ABSTRACT
Can we be - algebraically - exact about something approximate? We may, in the first instance, reject vigorously this seemingly 'indecent' thought. However, we should realize that the addition of the - from an applications point of view suggestive - adjective 'Computational' to subjects like 'Commutative Algebra' and 'Algebraic Geometry' in the past decades have provoked these thoughts. This is where the subject of this invited talk is coming from. And it turns out that what might have been initially a misunderstanding, leads to fascinating, new algebraic challenges. It follows from this line of thoughts that these new developments have been motivated by applications. This is the real starting point of this talk. Non-linear interactions between variables, or groups of variables describing a particular 'system' determine to a large extent its performance. But especially these interactions are difficult to capture. Methods based on first principles - or 'physical' models work well in simulations, but fail hopelessly in practice as the information these methods require is in no way covered by what is available in the form of measurements. This has led to the idea to construct model descriptions from the measurements, rather than imposing a model upon the system. To quote a famous, historical example in this connection, we are following here the traces of Johannes Kepler and Carl Friedrich Gauss in their model descriptions of the planet orbits around the sun based on observations because the physical state was, literally, unreachable. While this method works well in practice, it needs to be refined. Traditionally this type of problems is described from the onset in a real - or complex vector space setting. As a consequence combining different groups of variables, or, more suggestively subsystems comprising the total system, is accomplished through real - or complex numbers. But this means that the information about the - decisive - interactions is condensed in a number that is practically lost. This has led to the idea for the parameters gluing the different parts of the system together, rather than restricting them to be an element of a field, allowing them to be an element of a ring, specifically a polynomial ring. In this way these parameters reveal the interactions in the system under consideration. That this is a useful idea will be substantiated by a specific situation from oil industry where the total production from a group of - interacting - wells is considered and where the problem is to establish the contributions from the separate wells to the total production, acknowledging their interactions. A very short route that runs over Hilbert's Nullstellensatz [6] shows that the total production must be a member of the ideal generated by the separate productions. So this means that a really important industrial problem is 'just' a membership problem. That sounds almost too good to be true. And it is. Because nothing has been said about where the polynomials are coming from that are used in these considerations. In line with what has been stated above the polynomials have to be constructed from the data. But 'data' means more specifically noisy measurements. So whatever method is employed to construct the polynomials, they will be 'uncertain' objects. Uncertainty means here not only in terms of uncertain - real - coefficients, but also in terms of support and degree. Following Stetter [11], these polynomials are called Empirical Polynomials. Clearly this means that the confrontation of algebra with real-life applications is very brutal. Obviously there is no way that the membership problem mentioned above could be pursued in the 'normal' way.The talk then concentrates on a number of new, fascinating developments that are on going, with which the problems described above can be addressed. In particular the concept of an Approximate Vanishing Ideal is introduced, which is defined by the fact that there exists a system of generators of this ideal such that these generators 'almost vanish' - in the sense of small evaluations - on a given set of points. The Approximate Buchberger-Mller (ABM) algorithm is presented, a new algorithm derived from the classical BM algorithm - see [2], [8], and [1] - calculating Grbner -, Border - see [4], [5] - and Macaulay - see [9], [10] - Basis for the Approximate Vanishing Ideal. An interpretation of the Approximate Vanishing Ideal is that it reveals polynomial identities that are almost satisfied over the set of points under consideration. With reference to the problems described in the first paragraph it is noted that the Approximate Vanishing Ideal may be used to find polynomial expressions for the productions of oil wells, and for the total production of a group of wells. Next the problem is addressed how to calculate a 'sensible' ideal - that is different from the unit ideal - from a given collection of Empirical Polynomials. This is accomplished through an Approximate Border Basis Algorithm. Along the way, several new concepts are introduced - like Approximate Leading Coefficient and Approximate Leading Term - providing a solid algebraic foundation for these new developments. These developments culminate finally - for the time being - in addressing the - for the industrial applications so crucial - Approximate Membership for Zero-Dimensional Ideals. First of all it is stipulated why the standard method for solving the explicit membership problem - via the extended Buchberger algorithm, computing the syzygy module of the Grbner Basis, and transforming the syzygies - see [7] - fail in the approximate setting. In this approximate setting the approximate membership decision problem for zero-dimensional ideals is settled using the Approximate Vanishing Ideal, and completely reduced, orthogonal Macaulay Basis. Finally a solution is presented for the Approximate Explicit Membership for Zero-Dimensional Ideals, in which yet another new concept of an approximate normal form is a key element.Wherever possible the results are highlighted by examples using data from real-world problems.The closing remarks are reserved for our vision concerning this new development. Specifically we expect that realizing this program computationally will be a joint numerical - symbolic effort. The best candidate for the computer algebra part is in our view CoCoA - [3], [6], and [7] - in particular because of its superior library.Our developments are up till now still commutative, and with respect to addressing real-world problems absolutely communicative!. REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
INDEX TERMS
Primary Classification:
General Terms:
The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage Privacy Policy Code of Ethics Contact Us Useful downloads:  Adobe Acrobat
 QuickTime
 Windows Media Player
 Real Player
|
||||||||||||||||||||||||||||||||||||||||||||||||||||
Pdf
J.7