Alexander Kholodov, Institute of System Programming, Moscow, Russia

On algorithms of expansion of a given polynomial in Boas-Buck polynomial sequences


In many applications there is a problem of finding of coefficients of decomposition of the function on some basis, if the decomposition of this function on other basis is known. The important examples of such problems are funding decompositions of functions on Hermite and Laguerre polynomials. Inthe most general the given problem is reduced to a problem of multiplying N x matrices by N-vector. To do it is necassary to execute O(N^2) of arithmetic operations. The representations of transformation matrices as a product of Toeplitz and two diogonal matrices are found for decomposition of the polynomial in Hermite and Laguerre polynomials. It is sufficient of O(N logN), instead of O(N^2), as generally.