دانلود رایگان مقاله محاسبات بهینه از فضا دو بعدی و تعدد جهت دار از یک نقطه جدا شده

Abstract

Isolated singularities typically occur at self-intersection points of planar algebraic curves, curve offsets, intersections between spatial curves and surfaces, and so on. The information characterizing the singularity can be captured in a local dual basis, expressing combinations of vanishing derivatives at the singular point. Macaulay's algorithm is a classic algorithm for computing such a basis, for a point in an algebraic set. The integration method of Mourrain constructs much smaller matrices than Macaulay's approach, by performing integration on previously computed elements. In this work we are interested in the efficiency of dual basis computation, as well as its relation to orthogonal projection. First, we introduce an easy to implement criterion that avoids redundant computations during the computation of the dual basis, by deleting certain columns from the matrices in the integration method. In doing so, we explore general (non-monomial) bases for the associated primal quotient ring. Experiments show the efficient behavior of the improved method. Second, we introduce the notion of directional multiplicity, which expresses the multiplicity structure with respect to an axis, and is useful in understanding the geometry behind projection. We use this notion to shed light on the gap between the degree of the generator of the elimination ideal and the corresponding factor in the resultant.

5. Conclusions

There are two main algorithms for computing the orthogonal of an mζ -primary component of a given ideal. The first algorithm was given by Macaulay. Although it is still in use, and in spite of the improvements it saw since its inception, it is inefficient because of the construction of large matrices. The second algorithm, namely the integration method, reduces the size of the matrices drastically. In Mantzaflaris and Mourrain (2011), the authors found a way to avoid redundant computations by computing a primal base for the quotient of the mζ -primary ideal along with its dual base. This condition adds new rows to the matrices, which in some cases may lead to deleting those rows and some columns. Our work generalizes the method presented in Mantzaflaris and Mourrain (2011) in two ways. On one hand by introducing a criterion to avoid redundant computations, on the other hand by computing a general basis. This is done via computing a general basis for the quotient, which does not necessarily consist of monomials. Our method leads to deleting some columns from the matrices in the integration method instead of adding new rows. As shown in the benchmarks, the method produces consistently the smallest matrix among all methods tested. Moreover, in terms of practical performance, the benchmarks show that our implementation is consistently among the fastest of the methods tested. Another aspect studied in the present work is that of local properties and geometry of an isolated point via its directional multiplicity. This gives the multiplicity structure with respect to an axis, and is useful in understanding the geometry behind projection. Moreover, it sheds light on the gap between the degree of the generator of the elimination ideal and the corresponding factor in the resultant.