Construction of Janet Bases I. Monomial Bases
Algorithms for computation of Janet bases for monomial ideals and implementation of these algorithms are presented. As data structures for finite monomial sets the binary trees called Janet trees are selected. An algorithm for construction of a Janet basi
- PDF / 1,629,984 Bytes
- 15 Pages / 439.32 x 666.12 pts Page_size
- 111 Downloads / 216 Views
1
2
Abstract. Algorithms for computation of Janet bases for monomial ideals and implementation of these algorithms are presented. As data structures for finite monomial sets the binary trees called Janet trees are selected. An algorithm for construction of a Janet basis for the ideal generated by a finite monomial set is described. This algorithm contains as sub algorithms those to search for Janet divisor in a given tree and to insert monomials into the tree in the process of completion to involution. The algorithms presented have been implemented in C in the form of package for completion of monomial sets to Janet involutive ones. An example is given to illustrate practical efficiency of the monomial algorithms and their implementation.
1
Introduction
In papers [1-3] we invented a concept of involutive division, designed general algorithms for construction of polynomial involutive bases and studied a number of particular divisions. In paper [4] these algorithms were generalized to linear systems of partial differential equations. For Pommaret division the polynomial involutive algorithms were implemented in Reduce [1,5]. The algorithms for construction of monomial involutive bases and the computation of the Hilbert functions and Hilbert polynomials based on them were implemented in Mathematica [6]. The latter code designed for the general involutive division and written in the Mathematica language is much slower than the straightforward implementation of Janet division in C as we demonstrated in [6]. The Mathematica implementation has been recently extended to compute involutive polynomial and linear differential bases 1 . In the given paper we present algorithms and data structures to compute monomial Janet bases with particular features of Janet division taken into account. By this reason these algorithms are more efficient then those designed for the general involutive division and applied to construction of Janet bases. 1
The package is available at http://paul.math-inf.uni-greifswald.de/Invo;'
V. G. Ganzha et al. (eds.), Computer Algebra in Scientific Computing CASC 2001 © Springer-Verlag Berlin Heidelberg 2001
234
V. P. Gerdt, Y. A. Blinkov and D. A. Yanovich
The paper is organized as follows. Section 2 contains the necessary definitions and notations to be used in the sequel. In Section 3 we describe the data structure for a finite monomial set as a binary tree called Janet tree. The elements in the set are associated with the leaves of the tree. This data structure is amenable to efficient search for Janet divisor and for completion of monomial sets to Janet bases. An algorithm of the fast search for Janet divisor in a given tree is presented in Section 4. For this algorithm we give an estimation of its complexity in comparison to that of the classical binary search algorithm. In Section 5 we describe algorithms to insert into a given Janet tree of a monomial which has no involutive divisors among the leaf monomials in the tree and for computation of nonmultiplicative prolongations which arise
Data Loading...
