In a recent paper, Lima, Panario, and Wang have provided a new method to multiply polynomials expressed in Chebyshev basis which reduces the total number of multiplication for small degree polynomials. Although their ...
详细信息
In a recent paper, Lima, Panario, and Wang have provided a new method to multiply polynomials expressed in Chebyshev basis which reduces the total number of multiplication for small degree polynomials. Although their method uses Karatsuba's multiplication, a quadratic number of operations are still needed. In this paper, we extend their result by providing a complete reduction to polynomial multiplication in monomial basis, which therefore offers many subquadratic methods. Our reduction scheme does not rely on basis conversions and we demonstrate that it is efficient in practice. Finally, we show a linear time equivalence between the polynomial multiplication problem under monomial basis and under Chebyshev basis.
This paper considers structured matrix methods for the calculation of the theoretically exact roots of a polynomial whose coefficients are corrupted by noise, and whose exact form contains multiple roots. The addition...
详细信息
This paper considers structured matrix methods for the calculation of the theoretically exact roots of a polynomial whose coefficients are corrupted by noise, and whose exact form contains multiple roots. The addition of noise to the exact coefficients causes the multiple roots of the exact form of the polynomial to break up into simple roots, but the algorithms presented in this paper preserve the multiplicities of the roots. In particular, even though the given polynomial is corrupted by noise, and all computations are performed on these inexact coefficients, the algorithms 'sew' together the simple roots that originate from the same multiple root, thereby preserving the multiplicities of the roots of the theoretically exact form of the polynomial. The algorithms described in this paper do not require that the noise level imposed on the coefficients be known, and all parameters are calculated from the given inexact coefficients. Examples that demonstrate the theory are presented. (C) 2012 Elsevier B.V. All rights reserved.
In this paper, we present a new method for multiplying polynomials in Chebyshev form. Our approach has two steps. First, the well-known Karatsuba's algorithm is applied to polynomials constructed by using Chebyshe...
详细信息
In this paper, we present a new method for multiplying polynomials in Chebyshev form. Our approach has two steps. First, the well-known Karatsuba's algorithm is applied to polynomials constructed by using Chebyshev coefficients. Then, from the obtained result, extra arithmetic operations are used to write the final result in Chebyshev form. The proposed algorithm has a quadratic computational complexity. We also compare our method to other approaches.
We present an algebraic algorithm that computes the composition of two power series in softly linear time complexity. The previous best algorithms are O(n(1+o(1))) non-algebraic algorithm by Kedlaya and Umans (FOCS 20...
详细信息
ISBN:
(纸本)9798331516758;9798331516741
We present an algebraic algorithm that computes the composition of two power series in softly linear time complexity. The previous best algorithms are O(n(1+o(1))) non-algebraic algorithm by Kedlaya and Umans (FOCS 2008) and an O(n(1.43)) algebraic algorithm by Neiger, Salvy, Schost and Villard (JACM 2023). Our algorithm builds upon the recent Graeffe iteration approach to manipulate rational power series introduced by Bostan and Mori (SOSA 2021).
We show that the known list-decoding algorithms for univariate multiplicity and folded Reed-Solomon (FRS) codes can be made to run in (O) over tilde (n) time. Univariate multiplicity codes and FRS codes are natural va...
详细信息
ISBN:
(纸本)9798331516758;9798331516741
We show that the known list-decoding algorithms for univariate multiplicity and folded Reed-Solomon (FRS) codes can be made to run in (O) over tilde (n) time. Univariate multiplicity codes and FRS codes are natural variants of Reed-Solomon codes that were discovered and studied for their applications to list decoding. It is known that for every epsilon > 0, and rate r is an element of (0, 1), there exist explicit families of these codes that have rate r and can be list decoded from a (1 - r - epsilon) fraction of errors with constant list size in polynomial time (Guruswami & Wang (IEEE Trans. Inform. Theory 2013) and Kopparty, Ron-Zewi, Saraf & Wootters (SIAM J. Comput. 2023)). In this work, we present randomized algorithms that perform the above list-decoding tasks in (O) over tilde (n), where n is the block-length of the code. Our algorithms have two main components. The first component builds upon the lattice-based approach of Alekhnovich (IEEE Trans. Inf. Theory 2005), who designed a (O) over tilde (n) time list-decoding algorithm for Reed-Solomon codes approaching the Johnson radius. As part of the second component, we design (O) over tilde (n) time algorithms for two natural algebraic problems: given a (m+2)-variate polynomial Q(x, y(0), ... , y(m)) = (Q) over tilde (x) + Sigma(m)(i=0) Q(i)(x) . y(i) the first algorithm solves order-m linear differential equations of the form Q(x, f(x), df/dx, ... , d(m) f/dx(m)) equivalent to 0 while the second solves functional equations of the form Q(x, f(x), f(gamma x), ... , f(gamma(m) x)) equivalent to 0, where m is an arbitrary constant and gamma is a field element of sufficiently high order. These algorithms can be viewed as generalizations of classical (O) over tilde (n) time algorithms of Sieveking (Computing 1972) and Kung (Numer. Math. 1974) for computing the modular inverse of a power series, and might be of independent interest.
Bertini_real is a compiled command line program for numerically decomposing the real portion of a positive-dimensional complex component of an algebraic set. The software uses homotopy continuation to solve a series o...
详细信息
Bertini_real is a compiled command line program for numerically decomposing the real portion of a positive-dimensional complex component of an algebraic set. The software uses homotopy continuation to solve a series of systems via regeneration from a witness set to compute a cell decomposition. The implemented decomposition algorithms are similar to the well-known cylindrical algebraic decomposition (CAD) first established by Collins in that they produce a set of connected cells. In contrast to the CAD, Bertini_real produces cells with midpoints connected to boundary points by homotopies, which can easily be numerically tracked. Furthermore, the implemented decomposition for surfaces naturally yields a triangulation. This CAD-like decomposition captures the topological information and permits further computation on the real sets, such as sampling, visualization, and three-dimensional printing.
We show that the problem of finding an optimal stochastic blind controller in a Markov decision process is an NP-hard problem. The corresponding decision problem is NP-hard in PSPACE and SQRT-SUM-hard, hence placing i...
详细信息
We show that the problem of finding an optimal stochastic blind controller in a Markov decision process is an NP-hard problem. The corresponding decision problem is NP-hard in PSPACE and SQRT-SUM-hard, hence placing it in NP would imply breakthroughs in long-standing open problems in computer science. Our result establishes that the more general problem of stochastic controller optimization in POMDPs is also NP-hard. Nonetheless, we outline a special case that is convex and admits efficient global solutions.
暂无评论