Composing Power Series Over a Finite Ring in Essentially Linear Time |
| |
Affiliation: | Department of Mathematics, Statistics, and Computer Science, The University of Illinois at Chicago, Chicago, IL, 60607-7045, U.S.A. |
| |
Abstract: | Fix a finite commutative ringR. Letuandvbe power series overR, withv(0) = 0. This paper presents an algorithm that computes the firstnterms of the compositionu(v), given the firstnterms ofuandv, inn1 + o(1)ring operations. The algorithm is very fast in practice whenRhas small characteristic. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|