Tame Equivalence and Wild Sets

For semigroups with divisor theory we introduce an equivalence relation that preserves the p-dimensions of divisor class groups. While the approach has been motivated by the results on Hilbert-symbol equivalence in quadratic form theory over algebraic number fields, it is the purpose of the paper to generalize the setup to semigroups with divisor theory and to simplify the proofs by avoiding any ring- or number-theoretical arguments.     

Irreducible Algebraic Sets in Metabelian Groups

We present the construction for a u-product G₁ ○ G₂ of two u-groups G₁ and G₂, and prove that G₁ ○ G₂ is also a u-group and that every u-group, which contains G₁ and G₂ as subgroups and is generated by these, is a homomorphic image of G₁ ○ G₂. It is stated that if G is a u-group then the coordinate group of an affine space Gⁿ is equal to G ○ F_n, where F_n is a free metabelian group of rank n. Irreducible algebraic sets in G are treated for the case where G is a free metabelian group or wreath product of two free Abelian groups of finite ranks. __________ Translated from Algebra i Logika, Vol. 44, No. 5, pp. 601–621, September–October, 2005. Supported by RFBR grant No. 05-01-00292, by FP “Universities of Russia” grant No. 04.01.053, and by RF Ministry of Education grant No. E00-1.0-12.     

Voronoi Diagrams of Real Algebraic Sets

A collection of n (possibly singular) semi-algebraic sets in ^d of dimension d–1, each defined by polynomials of maximal degree , has ((n) ^d ) first-order Voronoi cells (for any fixed d). In the nonhypersurface case, where the maximal dimension of the semi-algebraic sets is m d–2, the number of first-order Voronoi cells is bounded above by O(n ^{m+1 d} ) (for nonsingular semi-algebraic sets) or by O((n) ^d ) (in general). The complexity of the entire kth-order Voronoi diagram of a generic collection of n non-singular real algebraic sets in R ^d of maximal dimension m<d and maximal degree is O(n ^{min(d+k,2d)2(m+1)d} ).     

Approximation of Analytic Sets with Proper Projection by Algebraic Sets

Let X be an analytic subset of U×C ⁿ of pure dimension k such that the projection of X onto U is a proper mapping, where U⊂C ^k is a Runge domain. We show that X can be approximated by algebraic sets. Next we present a constructive method for local approximation of analytic sets by algebraic ones.     

Algebraic Topology for Minimal Cantor Sets

It will be shown that every minimal Cantor set can be obtained as a projective limit of directed graphs. This allows to study minimal Cantor sets by algebraic topological means. In particular, homology, homotopy and cohomology are related to the dynamics of minimal Cantor sets. These techniques allow to explicitly illustrate the variety of dynamical behavior possible in minimal Cantor sets. submitted 20/07/05, accepted 18/10/05     

模糊T-粗糙集的代数性质

利用完备分配格L上t-模T,引进L上模糊T-粗糙集的概念,在此基础上定义模糊商集及其上、下近似的概念,研究它们的代数性质,得到若干结果。     

Algebraic Sets in A Divisible 2-Rigid Group

We answer the following question: Which finite unions of special irreducible algebraic sets in a divisible 2-rigid group are algebraic?     

Divide and Conquer Roadmap for Algebraic Sets

Let \(\mathrm{R}\) be a real closed field and \(\hbox {D}\subset \mathrm{R}\) an ordered domain. We describe an algorithm that given as input a polynomial \(P \in \hbox {D}[ X_{1} , \ldots ,X_{{ k}} ]\) and a finite set, \(\mathcal {A}= \{ p_{1} , \ldots ,p_{m} \}\) , of points contained in \(V= {\mathrm{{Zer}}} ( P, \mathrm{R}^{{ k}})\) described by real univariate representations, computes a roadmap of \(V\) containing \(\mathcal {A}\) . The complexity of the algorithm, measured by the number of arithmetic operations in \(\hbox {D}\) , is bounded by \(\big ( \sum _{i=1}^{m} D^{O ( \log ^{2} ( k ) )}_{i} +1 \big ) ( k^{\log ( k )} d )^{O ( k\log ^{2} ( k ))}\) , where \(d= \deg ( P )\) and \(D_{i}\) is the degree of the real univariate representation describing the point \(p_{i}\) . The best previous algorithm for this problem had complexity card \(( \mathcal {A} )^{O ( 1 )} d^{O ( k^{3/2} )}\) (Basu et al., ArXiv, 2012), where it is assumed that the degrees of the polynomials appearing in the representations of the points in \(\mathcal {A}\) are bounded by \(d^{O ( k )}\) . As an application of our result we prove that for any real algebraic subset \(V\) of \(\mathbb {R}^{k}\) defined by a polynomial of degree \(d\) , any connected component \(C\) of \(V\) contained in the unit ball, and any two points of \(C\) , there exists a semi-algebraic path connecting them in \(C\) , of length at most \(( k ^{\log (k )} d )^{O ( k\log ( k ) )}\) , consisting of at most \(( k ^{\log (k )} d )^{O ( k\log ( k ) )}\) curve segments of degrees bounded by \(( k ^{\log ( k )} d )^{O ( k \log ( k) )}\) . While it was known previously, by a result of D’Acunto and Kurdyka (Bull Lond Math Soc 38(6):951–965, 2006), that there always exists a path of length \(( O ( d ) )^{k-1}\) connecting two such points, there was no upper bound on the complexity of such a path.     

Numerically Computing Real Points on Algebraic Sets

Given a polynomial system f, a fundamental question is to determine if f has real roots. Many algorithms involving the use of infinitesimal deformations have been proposed to answer this question. In this article, we transform an approach of Rouillier, Roy, and Safey El Din, which is based on a classical optimization approach of Seidenberg, to develop a homotopy based approach for computing at least one point on each connected component of a real algebraic set. Examples are presented demonstrating the effectiveness of this parallelizable homotopy based approach.     

分片代数集合的不可约性和同构

本文利用多元样条函数来定义分片代数集合,讨论了分片代数集合的不可约性和同构问题,给出了分片代数集合不可约的两个等价条件,并把分片代数集合的同构分类问题转化为交换代数的同构分类问题。     

The Euclidean Distance Degree of an Algebraic Variety

The nearest point map of a real algebraic variety with respect to Euclidean distance is an algebraic function. For instance, for varieties of low-rank matrices, the Eckart–Young Theorem states that this map is given by the singular value decomposition. This article develops a theory of such nearest point maps from the perspective of computational algebraic geometry. The Euclidean distance degree of a variety is the number of critical points of the squared distance to a general point outside the variety. Focusing on varieties seen in applications, we present numerous tools for exact computations.     

On the Poles of Igusa's Local Zeta Function for Algebraic Sets

Let K be a p-adic field, let Z (s, f), sC, with Re(s) > 0,be the Igusa local zeta function associated to f(x) = (f₁(x),..., f_l(x)) [K (x₁, ..., x_n)]^l, and let be a Schwartz–Bruhatfunction. The aim of this paper is to describe explicitly thepoles of the meromorphic continuation of Z (s, f). Using resolutionof singularities it is possible to express Z (s, f) as a finitesum of p-adic monomial integrals. These monomial integrals arecomputed explicitly by using techniques of toroidal geometry.In this way, an explicit list of the candidates for poles ofZ (s, f) is obtained. 2000 Mathematics Subject Classification11S40, 14M25, 11D79.     

Sparse Approximations of the Schur Complement for Parallel Algebraic Hybrid Solvers in 3D

<正>In this paper we study the computational performance of variants of an algebraic additive Schwarz preconditioner for the Schur complement for the solution of large sparse linear systems.In earlier works,the local Schur complements were computed exactly using a sparse direct solver.The robustness of the preconditioner comes at the price of this memory and time intensive computation that is the main bottleneck of the approach for tackling huge problems.In this work we investigate the use of sparse approximation of the dense local Schur complements.These approximations are computed using a partial incomplete LU factorization.Such a numerical calculation is the core of the multi-level incomplete factorization such as the one implemented in pARMS. The numerical and computing performance of the new numerical scheme is illustrated on a set of large 3D convection-diffusion problems;preliminary experiments on linear systems arising from structural mechanics are also reported.     

Bounds For Gradient Trajectories and Geodesic Diameter of Real Algebraic Sets

Let M Rⁿ be a connected component of an algebraic set ^–1(0),where is a polynomial of degree d. Assume that M is containedin a ball of radius r. We prove that the geodesic diameter ofM is bounded by 2rv(n)d(4d–5)^n–2, where v(n) =(1/2)((n+1)/2)(n/2)^–1.This estimate is based on the bound rv(n)d(4d–5)^n–2for the length of the gradient trajectories of a linear projectionrestricted to M. 2000 Mathematics Subject Classification 32Bxx,34Cxx (primary), 32Sxx, 14P10 (secondary).     

Numerical Homotopies to Compute Generic Points on Positive Dimensional Algebraic Sets

Many applications modeled by polynomial systems have positive dimensional solution components (e.g., the path synthesis problems for four-bar mechanisms) that are challenging to compute numerically by homotopy continuation methods. A procedure of A. Sommese and C. Wampler consists in slicing the components with linear subspaces in general position to obtain generic points of the components as the isolated solutions of an auxiliary system. Since this requires the solution of a number of larger overdetermined systems, the procedure is computationally expensive and also wasteful because many solution paths diverge. In this article an embedding of the original polynomial system is presented, which leads to a sequence of homotopies, with solution paths leading to generic points of all components as the isolated solutions of an auxiliary system. The new procedure significantly reduces the number of paths to solutions that need to be followed. This approach has been implemented and applied to various polynomial systems, such as the cyclic n-roots problem.     

Efficient Smooth Stratification of an Algebraic Variety in Zero Characteristic and Its Applications

Consider a projective algebraic variety V defined as the set of common zeros of a family of homogeneous polynomials of degree less than d in variables with coefficients from a field k of zero characteristic. We prove that V can be represented as a union (respectively, a disjoint union) of at most (respectively, ) smooth quasiprojective algebraic varieties such that the degrees of these varieties are bounded from above by , where depends only on n. We propose algorithms for constructing regular sequences and sequences of local parameters for irreducible components of V and for computing the dimension of a real variety. The complexity of these algorithms is polynomial in the size of the input and in . Bibliography: 15 titles.     

Bilateral Fixed-Points and Algebraic Properties of Viability Kernels and Capture Basins of Sets

Many concepts of viability theory such as viability or invariance kernels and capture or absorption basins under discrete multivalued systems, differential inclusions and dynamical games share algebraic properties that provide simple – yet powerful – characterizations as either largest or smallest fixed points or unique minimax (or bilateral fixed-point) of adequate maps defined on pairs of subsets. Further, important algorithms such as the Saint-Pierre viability kernel algorithm for computing viability kernels under discrete system and the Cardaliaguet algorithm for characterizing discriminating kernels under dynamical games are algebraic in nature. The Matheron Theorem as well as the Galois transform find applications in the field of control and dynamical games allowing us to clarify concepts and simplify proofs.