اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدComputing solutions of linear Mahler equations
139
0
0.0
(
0
)
نشر من قبل
Fr\\'ed\\'eric Chyzak
تاريخ النشر
2016
مجال البحث
الهندسة المعلوماتية
والبحث باللغة
English
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Mahler equations relate evaluations of the same function $f$ at iterated $b$th powers of the variable. They arise in particular in the study of automatic sequences and in the complexity analysis of divide-and-conquer algorithms. Recently, the problem of solving Mahler equations in closed form has occurred in connection with number-theoretic questions. A difficulty in the manipulation of Mahler equations is the exponential blow-up of degrees when applying a Mahler operator to a polynomial. In this work, we present algorithms for solving linear Mahler equations for series, polynomials, and rational functions, and get polynomial-time complexity under a mild assumption. Incidentally, we develop an algorithm for computing the gcrd of a family of linear Mahler operators.
قيم البحث
اقرأ أيضاً
In this paper we report on an application of computer algebra in which mathematical puzzles are generated of a type that had been widely used in mathematics contests by a large number of participants worldwide. The algorithmic aspect of our work pr
ovides a method to compute rational solutions of single polynomial equations that are typically large with $10^2 ldots 10^5$ terms and that are heavily underdetermined. This functionality was obtained by adding modules for a new type of splitting of equations to the existing package CRACK that is normally used to solve polynomial algebraic and differential systems.
This paper is devoted to the study of the analytic properties of Mahler systems at 0. We give an effective characterisation of Mahler systems that are regular singular at 0, that is, systems which are equivalent to constant ones. Similar characterisa
tions already exist for differential and (q-)difference systems but they do not apply in the Mahler case. This work fill in the gap by giving an algorithm which decides whether or not a Mahler system is regular singular at 0.
We start with elementary algebraic theory of factorization of linear ordinary differential equations developed in the period 1880-1930. After exposing these classical results we sketch more sophisticated algorithmic approaches developed in the last 2
0 years. The main part of this paper is devoted to modern generalizations of the notion of factorization to the case of systems of linear partial differential equations and their relation with explicit solvability of nonlinear partial differential equations based on some constructions from the theory of abelian categories.
The class of quasiseparable matrices is defined by a pair of bounds, called the quasiseparable orders, on the ranks of the maximal sub-matrices entirely located in their strictly lower and upper triangular parts. These arise naturally in applications
, as e.g. the inverse of band matrices, and are widely used for they admit structured representations allowing to compute with them in time linear in the dimension and quadratic with the quasiseparable order. We show, in this paper, the connection between the notion of quasisepa-rability and the rank profile matrix invariant, presented in [Dumas & al. ISSAC15]. This allows us to propose an algorithm computing the quasiseparable orders (rL, rU) in time O(n^2 s^($omega$--2)) where s = max(rL, rU) and $omega$ the exponent of matrix multiplication. We then present two new structured representations, a binary tree of PLUQ decompositions, and the Bruhat generator, using respectively O(ns log n/s) and O(ns) field elements instead of O(ns^2) for the previously known generators. We present algorithms computing these representations in time O(n^2 s^($omega$--2)). These representations allow a matrix-vector product in time linear in the size of their representation. Lastly we show how to multiply two such structured matrices in time O(n^2 s^($omega$--2)).
Solving linear systems of equations is ubiquitous in all areas of science and engineering. With rapidly growing data sets, such a task can be intractable for classical computers, as the best known classical algorithms require a time proportional to t
he number of variables N. A recently proposed quantum algorithm shows that quantum computers could solve linear systems in a time scale of order log(N), giving an exponential speedup over classical computers. Here we realize the simplest instance of this algorithm, solving 2*2 linear equations for various input vectors on a quantum computer. We use four quantum bits and four controlled logic gates to implement every subroutine required, demonstrating the working principle of this algorithm.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
