Newton's method is an ubiquitous tool to solve equations, both in the archimedean and non-archimedean settings D for which it does not really differ. Broyden was the instigator of what is called "quasi-Newton...
详细信息
ISBN:
(纸本)9781450371001
Newton's method is an ubiquitous tool to solve equations, both in the archimedean and non-archimedean settings D for which it does not really differ. Broyden was the instigator of what is called "quasi-Newton methods". These methods use an iteration step where one does not need to compute a complete Jacobian matrix nor its inverse. We provide an adaptation of Broyden's method in a general non-archimedean setting, compatible with the lack of inner product, and study its Q and R convergence. We prove that our adapted method converges at least Q-linearly and R-superlinearly with R-order 2(1/2m). in dimension m. Numerical data are provided.
Let K be a field equipped with a valuation. Tropical varieties over K can be defined with a theory of GrObner bases taking into account the valuation of K. Because of the use of the valuation, this theory is promising...
详细信息
Let K be a field equipped with a valuation. Tropical varieties over K can be defined with a theory of GrObner bases taking into account the valuation of K. Because of the use of the valuation, this theory is promising for stable computations over polynomial rings over a p-adic field. We design a strategy to compute such tropical GrObner bases by adapting the Matrix-F5 algorithm. Two variants of the Matrix-F5 algorithm, depending on how the Macaulay matrices are built, are available to tropical computation with respective modifications. The former is more numerically stable while the latter is faster. Our study is performed both over any exact field with valuation and some inexact fields like Q(p) or F-q((t)). In the latter case, we track the loss in precision, and show that the numerical stability can compare very favorably to the case of classical Grobner bases when the valuation is non-trivial. Numerical examples are provided. (C) 2017 Elsevier Ltd. All rights reserved.
Let (f(1,) . . . ,f(s)) is an element of Q(p) [X-1,X- . . . ,X-n](s) be a sequence of homogeneous polynomials with p-adic coefficients. Such system may happen, for example, in arithmetic geometry. Yet, since Q(p) is n...
详细信息
Let (f(1,) . . . ,f(s)) is an element of Q(p) [X-1,X- . . . ,X-n](s) be a sequence of homogeneous polynomials with p-adic coefficients. Such system may happen, for example, in arithmetic geometry. Yet, since Q(p) is not an effective field, classical algorithm does not apply. We provide a definition for an approximate Grobner basis with respect to a monomial order w. We design a strategy to compute such a basis, when precision is enough and under the assumption that the input sequence is regular and the ideals < f(1), . . . , f(i)> are weakly-w-ideals. The conjecture of Moreno-Socias states that for the grevlex ordering, such sequences are generic. Two variants of that strategy are available, depending on whether one leans more on precision or time-complexity. For the analysis of these algorithms, we study the loss of precision of the Gauss row echelon algorithm, and apply it to an adapted Matrix-F5 algorithm. Numerical examples are provided. Moreover, the fact that under such hypotheses, Grobner bases can be computed stably has many applications. Firstly, the mapping sending (f(1,) . . . , f(s)) to the reduced Grobner basis of the ideal they span is differentiable, and its differential can be given explicitly. Secondly, these hypotheses allow to perform lifting on the Grobner bases, from Z/p(k)Z to Z/p(k+k')Z or Z. Finally, asking for the same hypotheses on the highest-degree homogeneous components of the entry polynomials allows to extend our strategy to the affine case. (C) 2016 Elsevier Ltd. All rights reserved.
Let K be a field equipped with a valuation. Tropical varieties over K can be defined with a theory of Grobner bases taking into account the valuation of K. Because of the use of the valuation, this theory is promising...
详细信息
ISBN:
(纸本)9781450334358
Let K be a field equipped with a valuation. Tropical varieties over K can be defined with a theory of Grobner bases taking into account the valuation of K. Because of the use of the valuation, this theory is promising for stable computations over polynomial rings over a p-adic fields. We design a strategy to compute such tropical Grobner bases by adapting the Matrix-F5 algorithm. Two variants of the Matrix-F5 algorithm, depending on how the Macaulay matrices are built, are available to tropical computation with respective modifications. The former is more numerically stable while the latter is faster. Our study is performed both over any exact field with valuation and some inexact fields like Q(p) or F-q [t]. In the latter case, we track the loss in precision, and show that the numerical stability can compare very favorably to the case of classical Grobner bases when the valuation is non-trivial. Numerical examples are provided.
暂无评论