Prof. Eugene Zima (Wilfrid Laurier University, Waterloo, Canada) will be visiting Kobe University from March 10 to March 31, 2009.
He will give a series of the following lectures. Two of the lectures (on March 17 and 23) coincide with broader seminars or meetings.
In these lectures we will discuss several different techniques for accelerating computations in different domains, as well as various applications.
The first technique discussed is known as "Chains of recurrences". Chains of recurrences technique was introduced as an "aggressive" technique for loop optimization. It was later extended to multidimensional case that corresponds to the nested loop optimization problem and was used to accelerate massive numeric computations over the regular intervals in such applications as for example mathematical plotting. Recently this technique in very rudimentary form was adopted by compiler developers. For example it has been adopted in the well-known mainstream GCC 4.0 compiler. We discuss this technique with applications together with several our own (Maple, C, Java, VHDL) implementations.
The second group of techniques is concerned with fast precision evaluation of hypergeometric series. Many important constants, such as exp(1) and Apery's constant zeta(3), can be approximated by a truncated hypergeometric series. The evaluation of such series to high precision has traditionally been done by binary splitting followed by fixed-point division. However, the numerator and the denominator computed by binary splitting usually contain a very large common factor. We discuss application of several standard computer algebra techniques, including modular computation and rational reconstruction, to overcome these shortcomings. The space complexity of our algorithm is the same as a bound on the size of the reduced numerator and denominator of the series approximation. Moreover, if the predicted bound is small, the time complexity is better than the standard binary splitting approach. Our approach allows a series to be evaluated to a higher precision without additional memory. We show that when our algorithm is applied to compute zeta(3), the memory requirement is significantly reduced.
Modern algorithmic treatment of the summation (indefinite and definite), that leads to immediate implementation on a computer, has started with works of S.A. Abramov (1971), G. Gosper (1977), D. Zeilberger (1991). Many improvements of the summation algorithms and theoretical foundations of algorithmic approach were proposed and implemented by M. Bronstein, F. Chyzak, J. Gerhard, M. van Hoeij, P. Paule, M. Petkovsek, B. Salvy, V. Strehl, N. Takayama, H. Wilf, and others. These improvements make symbolic summation in computer algebra systems pretty useful. On the other hand integral representation approach to the evaluation of combinatorial sums developed by G.P. Egorychev (1970-80) was (and is) mainly used for cracking hard combinatorial sums "by hand".
In these lectures we give a brief overview of well-known summation algorithms used in computer algebra systems such as Maple, describe recent developments in algorithmic summation and establish links between them and methods of integral representation. Revisions of "standard" algorithms from the integral representation point of view sometimes lead to further developments and improvements in run-time complexity. We provide wide variety of examples together with samples of experimental implementations in Maple.
The lectures will be held in the buildings B or Z
of the Rokkodai campus of Kobe University;
they are situated between the marks "12" and "28"
on this map.
For more information, please contact Dr. Raimundas Vidunas