The Experts below are selected from a list of 30729 Experts worldwide ranked by ideXlab platform
Ioannis Z Emiris - One of the best experts on this subject based on the ideXlab platform.
-
on the complexity of real root isolation using continued Fractions
Theoretical Computer Science, 2008Co-Authors: Elias Tsigaridas, Ioannis Z EmirisAbstract:We present algorithmic, complexity and implementation results concerning real root isolation of integer univariate polynomials using the continued Fraction Expansion of real algebraic numbers. One motivation is to explain the method's good performance in practice. We derive an expected complexity bound of [email protected]?"B(d^6+d^[email protected]^2), where d is the polynomial degree and @t bounds the coefficient bit size, using a standard bound on the expected bit size of the integers in the continued Fraction Expansion, thus matching the current worst-case complexity bound for real root isolation by exact methods (Sturm, Descartes and Bernstein subdivision). Moreover, using a homothetic transformation we improve the expected complexity bound to [email protected]?"B(d^[email protected]). We compute the multiplicities within the same complexity and extend the algorithm to non-square-free polynomials. Finally, we present an open-source C++ implementation in the algebraic library synaps, and illustrate its completeness and efficiency as compared to some other available software. For this we use polynomials with coefficient bit size up to 8000 bits and degree up to 1000.
-
univariate polynomial real root isolation continued Fractions revisited
European Symposium on Algorithms, 2006Co-Authors: Elias Tsigaridas, Ioannis Z EmirisAbstract:We present algorithmic, complexity and implementation results concerning real root isolation of integer univariate polynomials using the continued Fraction Expansion of real numbers. We improve the previously known bound by a factor of d T, where d is the polynomial degree and T bounds the coefficient bitsize, thus matching the current record complexity for real root isolation by exact methods. Namely, the complexity bound is O˜B(d4T2) using a standard bound on the expected bitsize of the integers in the continued Fraction Expansion. We show how to compute the multiplicities within the same complexity and extend the algorithm to non square-free polynomials. Finally, we present an efficient open-source C++ implementation in the algebraic library synaps, and illustrate its efficiency as compared to other available software. We use polynomials with coefficient bitsize up to 8000 and degree up to 1000.
-
univariate polynomial real root isolation continued Fractions revisited
arXiv: Symbolic Computation, 2006Co-Authors: Elias Tsigaridas, Ioannis Z EmirisAbstract:We present algorithmic, complexity and implementation results concerning real root isolation of integer univariate polynomials using the continued Fraction Expansion of real algebraic numbers. One motivation is to explain the method's good performance in practice. We improve the previously known bound by a factor of $d \tau$, where $d$ is the polynomial degree and $\tau$ bounds the coefficient bitsize, thus matching the current record complexity for real root isolation by exact methods. Namely, the complexity bound is $\sOB(d^4 \tau^2)$ using the standard bound on the expected bitsize of the integers in the continued Fraction Expansion. We show how to compute the multiplicities within the same complexity and extend the algorithm to non square-free polynomials. Finally, we present an efficient open-source \texttt{C++} implementation in the algebraic library \synaps, and illustrate its efficiency as compared to other available software. We use polynomials with coefficient bitsize up to 8000 and degree up to 1000.
Elias Tsigaridas - One of the best experts on this subject based on the ideXlab platform.
-
on continued Fraction Expansion of real roots of polynomial systems complexity and condition numbers
Theoretical Computer Science, 2011Co-Authors: Angelos Mantzaflaris, Bernard Mourrain, Elias TsigaridasAbstract:We elaborate on a correspondence between the coefficients of a multivariate polynomial represented in the Bernstein basis and in a tensor-monomial basis, which leads to homography representations of polynomial functions that use only integer arithmetic (in contrast to the Bernstein basis) and are feasible over unbounded regions. Then, we study an algorithm to split this representation and obtain a subdivision scheme for the domain of multivariate polynomial functions. This implies a new algorithm for real root isolation, MCF, that generalizes the Continued Fraction (CF) algorithm of univariate polynomials. A partial extension of Vincent's Theorem for multivariate polynomials is presented, which allows us to prove the termination of the algorithm. Bounding functions, projection and preconditioning are employed to speed up the scheme. The resulting isolation boxes have optimized rational coordinates, corresponding to the first terms of the continued Fraction Expansion of the real roots. Finally, we present new complexity bounds for a simplified version of the algorithm in the bit complexity model, and also bounds in the real RAM model for a family of subdivision algorithms in terms of the real condition number of the system. Examples computed with our C++ implementation illustrate the practical aspects of our method.
-
on the complexity of real root isolation using continued Fractions
Theoretical Computer Science, 2008Co-Authors: Elias Tsigaridas, Ioannis Z EmirisAbstract:We present algorithmic, complexity and implementation results concerning real root isolation of integer univariate polynomials using the continued Fraction Expansion of real algebraic numbers. One motivation is to explain the method's good performance in practice. We derive an expected complexity bound of [email protected]?"B(d^6+d^[email protected]^2), where d is the polynomial degree and @t bounds the coefficient bit size, using a standard bound on the expected bit size of the integers in the continued Fraction Expansion, thus matching the current worst-case complexity bound for real root isolation by exact methods (Sturm, Descartes and Bernstein subdivision). Moreover, using a homothetic transformation we improve the expected complexity bound to [email protected]?"B(d^[email protected]). We compute the multiplicities within the same complexity and extend the algorithm to non-square-free polynomials. Finally, we present an open-source C++ implementation in the algebraic library synaps, and illustrate its completeness and efficiency as compared to some other available software. For this we use polynomials with coefficient bit size up to 8000 bits and degree up to 1000.
-
univariate polynomial real root isolation continued Fractions revisited
European Symposium on Algorithms, 2006Co-Authors: Elias Tsigaridas, Ioannis Z EmirisAbstract:We present algorithmic, complexity and implementation results concerning real root isolation of integer univariate polynomials using the continued Fraction Expansion of real numbers. We improve the previously known bound by a factor of d T, where d is the polynomial degree and T bounds the coefficient bitsize, thus matching the current record complexity for real root isolation by exact methods. Namely, the complexity bound is O˜B(d4T2) using a standard bound on the expected bitsize of the integers in the continued Fraction Expansion. We show how to compute the multiplicities within the same complexity and extend the algorithm to non square-free polynomials. Finally, we present an efficient open-source C++ implementation in the algebraic library synaps, and illustrate its efficiency as compared to other available software. We use polynomials with coefficient bitsize up to 8000 and degree up to 1000.
-
univariate polynomial real root isolation continued Fractions revisited
arXiv: Symbolic Computation, 2006Co-Authors: Elias Tsigaridas, Ioannis Z EmirisAbstract:We present algorithmic, complexity and implementation results concerning real root isolation of integer univariate polynomials using the continued Fraction Expansion of real algebraic numbers. One motivation is to explain the method's good performance in practice. We improve the previously known bound by a factor of $d \tau$, where $d$ is the polynomial degree and $\tau$ bounds the coefficient bitsize, thus matching the current record complexity for real root isolation by exact methods. Namely, the complexity bound is $\sOB(d^4 \tau^2)$ using the standard bound on the expected bitsize of the integers in the continued Fraction Expansion. We show how to compute the multiplicities within the same complexity and extend the algorithm to non square-free polynomials. Finally, we present an efficient open-source \texttt{C++} implementation in the algebraic library \synaps, and illustrate its efficiency as compared to other available software. We use polynomials with coefficient bitsize up to 8000 and degree up to 1000.
Andrew N W Hone - One of the best experts on this subject based on the ideXlab platform.
-
continued Fractions and irrationality exponents for modified engel and pierce series
arXiv: Number Theory, 2018Co-Authors: Andrew N W Hone, Juan L VaronaAbstract:An Engel series is a sum of reciprocals of a non-decreasing sequence $(x_n)$ of positive integers, which is such that each term is divisible by the previous one, and a Pierce series is an alternating sum of the reciprocals of a sequence with the same property. Given an arbitrary rational number, we show that there is a family of Engel series which when added to it produces a transcendental number $\alpha$ whose continued Fraction Expansion is determined explicitly by the corresponding sequence $(x_n)$, where the latter is generated by a certain nonlinear recurrence of second order. We also present an analogous result for a rational number with a Pierce series added to or subtracted from it. In both situations (a rational number combined with either an Engel or a Pierce series), the irrationality exponent is bounded below by $(3+\sqrt{5})/2$, and we further identify infinite families of transcendental numbers $\alpha$ whose irrationality exponent can be computed precisely. In addition, we construct the continued Fraction Expansion for an arbitrary rational number added to an Engel series with the stronger property that $x_j^2$ divides $x_{j+1}$ for all $j$.
-
continued Fractions and irrationality exponents for modified engel and pierce series
arXiv: Number Theory, 2018Co-Authors: Andrew N W Hone, Juan L VaronaAbstract:An Engel series is a sum of reciprocals of a non-decreasing sequence $(x_n)$ of positive integers, which is such that each term is divisible by the previous one, and a Pierce series is an alternating sum of the reciprocals of a sequence with the same property. Given an arbitrary rational number, we show that there is a family of Engel series which when added to it produces a transcendental number $\alpha$ whose continued Fraction Expansion is determined explicitly by the corresponding sequence $(x_n)$, where the latter is generated by a certain nonlinear recurrence of second order. We also present an analogous result for a rational number with a Pierce series added to or subtracted from it. In both situations (a rational number combined with either an Engel or a Pierce series), the irrationality exponent is bounded below by $(3+\sqrt{5})/2$, and we further identify infinite families of transcendental numbers $\alpha$ whose irrationality exponent can be computed precisely. In addition, we construct the continued Fraction Expansion for an arbitrary rational number added to an Engel series with the stronger property that $x_j^2$ divides $x_{j+1}$ for all $j$.
-
on the continued Fraction Expansion of certain engel series
Journal of Number Theory, 2016Co-Authors: Andrew N W HoneAbstract:Abstract Text An Engel series is a sum of the reciprocals of an increasing sequence of positive integers, which is such that each term is divisible by the previous one. Here we consider a particular class of Engel series, for which each term of the sequence is divisible by the square of the preceding one, and find an explicit expression for the continued Fraction Expansion of the sum of a generic series of this kind. As a special case, this includes certain series whose continued Fraction Expansion was found by Shallit. A family of examples generated by nonlinear recurrences with the Laurent property is considered in detail, along with some associated transcendental numbers. Video For a video summary of this paper, please visit https://youtu.be/T7OL_rKI8Z8 .
-
on the continued Fraction Expansion of certain engel series
arXiv: Number Theory, 2015Co-Authors: Andrew N W HoneAbstract:An Engel series is a sum of the reciprocals of an increasing sequence of positive integers, which is such that each term is divisible by the previous one. Here we consider a particular class of Engel series, for which each term of the sequence is divisible by the square of the preceding one, and find an explicit expression for the continued Fraction Expansion of the sum of a generic series of this kind. As a special case, this includes certain series whose continued Fraction Expansion was found by Shallit. A family of examples generated by nonlinear recurrences with the Laurent property is considered in detail, along with some associated transcendental numbers.
Balazs Bank - One of the best experts on this subject based on the ideXlab platform.
-
converting series biquad filters into delayed parallel form application to graphic equalizers
IEEE Transactions on Signal Processing, 2019Co-Authors: Juho Liski, Balazs Bank, Julius O Smith, Vesa ValimakiAbstract:Digital filter transfer functions can be converted between the direct form and parallel connections of elementary sections, typically second-order (“biquad”) sections. The conversion from direct to parallel form is performed using a partial Fraction Expansion, which usually requires long division of polynomials when expanding proper and improper transfer functions. This paper focuses on the conversion of a series of biquad sections to the parallel form, and proposes a novel way to implement the partial-Fraction Expansion without the use of long division. Additionally, the resulting structure is the delayed parallel form in which the section gains remain small. The new design and previous methods are compared in a case study on graphic equalizer design. The delayed parallel filter is shown to use the same number of operations as the series form during filtering. The conversion of a recently proposed series graphic equalizer into the delayed parallel form leads to an improved parallel graphic equalizer design relative to all known prior approaches. The proposed conversion technique is widely applicable to the design of parallel infinite impulse response filters, which are becoming popular as they are well suited to implementation using parallel computers.
-
converting infinite impulse response filters to parallel form tips tricks
IEEE Signal Processing Magazine, 2018Co-Authors: Balazs BankAbstract:Discrete-time rational transfer functions are often converted to parallel second-order sections due to better numerical performance compared to direct form infinite impulse response (IIR) implementations. This is usually done by performing partial Fraction Expansion over the original transfer function. When the order of the numerator polynomial is greater or equal to that of the denominator, polynomial long division is applied before partial Fraction Expansion resulting in a parallel finite impulse response (FIR) path.
Vesa Valimaki - One of the best experts on this subject based on the ideXlab platform.
-
converting series biquad filters into delayed parallel form application to graphic equalizers
IEEE Transactions on Signal Processing, 2019Co-Authors: Juho Liski, Balazs Bank, Julius O Smith, Vesa ValimakiAbstract:Digital filter transfer functions can be converted between the direct form and parallel connections of elementary sections, typically second-order (“biquad”) sections. The conversion from direct to parallel form is performed using a partial Fraction Expansion, which usually requires long division of polynomials when expanding proper and improper transfer functions. This paper focuses on the conversion of a series of biquad sections to the parallel form, and proposes a novel way to implement the partial-Fraction Expansion without the use of long division. Additionally, the resulting structure is the delayed parallel form in which the section gains remain small. The new design and previous methods are compared in a case study on graphic equalizer design. The delayed parallel filter is shown to use the same number of operations as the series form during filtering. The conversion of a recently proposed series graphic equalizer into the delayed parallel form leads to an improved parallel graphic equalizer design relative to all known prior approaches. The proposed conversion technique is widely applicable to the design of parallel infinite impulse response filters, which are becoming popular as they are well suited to implementation using parallel computers.
