This paper studies digit-cost functions for the Euclid algorithm on polynomials with coefficients in a finite field, in terms of the number of operations performed on the finite field F-q. The usual bit-complexity is ...
详细信息
This paper studies digit-cost functions for the Euclid algorithm on polynomials with coefficients in a finite field, in terms of the number of operations performed on the finite field F-q. The usual bit-complexity is defined with respect to the degree of the quotients;we focus here on a notion of 'fine' complexity (and on associated costs) which relies on the number of their non-zero coefficients. It also considers and compares the ergodic behavior of the corresponding costs for truncated trajectories under the action of the Gauss map acting on the set of formal power series with coefficients in a finite field. The present paper is thus mainly interested in the study of the probabilistic behavior of the corresponding random variables: average estimates (expectation and variance) are obtained in a purely combinatorial way thanks to classical methods in combinatorial analysis (more precisely, bivariate generating functions);some of our costs are even proved to satisfy an asymptotic Gaussian law. We also relate this study with a Farey algorithm which is a refinement of the continued fraction algorithm for the set of formal power series with coefficients in a finite field: this algorithm discovers 'step by step' each non-zero monomial of the quotient, so its number of steps is closely related to the number of non-zero coefficients. In particular, this map is shown to admit a finite invariant measure in contrast with the real case. This version of the Farey map also produces mediant convergents in the continued fraction expansion of formal power series with coefficients in a finite field. (C) 2014 Elsevier Inc. All rights reserved.
Computation of the sign of the determinant of a matrix and the determinantitself is a challenge for both numerical and exact methods. We survey the complexity of existingmethods to solve these problems when the input ...
详细信息
Computation of the sign of the determinant of a matrix and the determinantitself is a challenge for both numerical and exact methods. We survey the complexity of existingmethods to solve these problems when the input is an n * n matrix A with integer entries. We studythe bit-complexities of the algorithms asymptotically in n and the norm of A. Existing approachesrely on numerical approximate computations, on exact computations, or on both types of arithmetic incombination.
We study a class of Euclidean algorithms related to divisions where the remainder is constrained to belong to [alpha-1, alpha], for some alpha is an element of [0, 1]. The paper is devoted to the average-case analysis...
详细信息
We study a class of Euclidean algorithms related to divisions where the remainder is constrained to belong to [alpha-1, alpha], for some alpha is an element of [0, 1]. The paper is devoted to the average-case analysis of these algorithms, in terms of number of steps or bit-complexity. This is a new instance of the so-called "dynarnical analysis" method, where dynamical systems are made a deep use of. Here, the dynamical systems of interest have an infinite number of branches and they axe not Markovian, so that the general framework of dynamical analysis is more complex to adapt to this case than previously. (C) 2002 Elsevier Science (USA). All rights reserved.
Subdivision-based algorithms recursively subdivide an input region until the smaller subregions can be processed. It is a challenge to analyze the complexity of such algorithms because the work they perform is not uni...
详细信息
Subdivision-based algorithms recursively subdivide an input region until the smaller subregions can be processed. It is a challenge to analyze the complexity of such algorithms because the work they perform is not uniform across the input region. Continuous amortization was introduced in Burr et al. (2009) as a way to bound the complexity of subdivision-based algorithms. The main features of this new technique are that (1) the technique can be applied, uniformly, to a variety of subdivision-based algorithms, (2) the technique considers a function directly related to the subdivision-based algorithm under consideration, and (3) the output of the technique is often explicitly expressed in terms of the intrinsic complexity of the problem instance. In this paper, the theory of continuous amortization is generalized and applied in several directions. The theory is generalized (1) to allow the domain to be higher dimensional or an abstract measure space, (2) to allow more general subdivisions than bisections, and (3) to bound the value of general functions on the regions of the final partition. The theory is applied to seven examples of subdivision-based algorithms. These applications include (1) bounding the number of subdivisions performed by algorithms for isolating real and complex roots of polynomials, (2) bounding the bit-complexity of subdivision-based algorithms for isolating the real roots of polynomials, and (3) bounding the expected run-time of an algorithm for approximating a biased coin. In each of these applications, by using continuous amortization, we achieve or improve the best-known complexity bounds. (C) 2016 Elsevier Ltd. All rights reserved.
We address univariate root isolation when the polynomial's coefficients are in a multiple field extension. We consider a polynomial F is an element of L[Y], where L is a multiple algebraic extension of Q. We provi...
详细信息
ISBN:
(纸本)9798400700392
We address univariate root isolation when the polynomial's coefficients are in a multiple field extension. We consider a polynomial F is an element of L[Y], where L is a multiple algebraic extension of Q. We provide aggregate bounds for F and algorithmic and bit-complexity results for the problem of isolating its roots. For the latter problem we follow a common approach based on univariate root isolation algorithms. For the particular case where F does not have multiple roots, we achieve a bit-complexity in (O) over tilde (B) (nd(2n+2) (d +n tau)), where tau is the total degree and.. is the bitsize of the involved polynomials. In the general case we need to enhance our algorithm with a preprocessing step that determines the number of distinct roots of F. We follow a numerical, yet certified, approach that has bit-complexity e (O) over tilde (B) (n(2)d(3n+3)tau + n(3)d(2n+4)tau).
暂无评论