Abstract:
Toom-Cook strategy is a well-known method for building algorithms to
efficiently multiply dense univariate polynomials. Efficiency of the
algorithm depends on the choice of some interpolation points and on
the exact sequence of operation for evaluation and interpolation.
There are asymptotically faster methods, but, when carefully tuned,
Toom-Cook algorithm can be the fastest for a wide range of inputs.
Here we give a method to find the faster Toom-Cook algorithm for any
given splitting order, and the results found for polynomials in
characteristic 2.
Some effort was spent in order to extend Toom algorithms to multivariate
dense homogeneous polynomials.
To appear: Proceedings of WAIFI 2007.
Download: PDF-paper, software.
Abstract: Nel calcolo delle basi di Gröbner, il problema di eseguire i calcoli con coefficienti numerici e/o dati inesatti è tutt'ora aperto. Può accadere, per accumulazione di errori o per una insufficiente precisione di lavoro, che il risultato non sia quello teoricamente atteso. La base può avere piú o meno polinomi, un diverso numero di soluzioni, un insieme di zeri con molteplicità errata e cosí via. Aumentare la precisione può limitare la propagazione degli errori, ma non possiamo sapere in anticipo quanto questa debba essere e spesso l'unico approccio possibilie sonsiste in ripetuti tentativi ed errori. Gestire dati intrinsecamente inesatti è un compito ancora piú complesso. In questo articolo l'uso combinato delle sizigie e dell'aritmetica degli intervalli viene proposta come tecnica per decidere, ad ogni punto critico dell'algoritmo, come proseguire.
Pubblicato: (versione ridotta) Proceedings of the 6th SYNASC Symposium. D. Petcu, D. Zaharie, V. Negru, T. Jebelean ed. MIRTON, Timişoara, Romania 2004, pp. 77 - 89, ISBN 973-661-441-7
Pubblicato: (version estesa) Analele Universitatii din Timisoara, Vol. XLII, Fasc.special 2, T. Jebelean, V. Negru, A. Popovici ed., Timişoara, Romania 2004, pp. 13 - 30, ISSN 1224-970X
Scaricare: PDF-paper, software.
Abstract: In Gröbner bases computation, as in other algorithms in commutative algebra, a general open question is how to guide the calculations coping with numerical coefficients and/or not exact input data. It often happens that, due to error accumulation and/or insufficient working precision, the obtained result is not one expects from a theoretical derivation. The resulting basis may have more or less polynomials, a different number of solution, roots with different multiplicity, another Hilbert function, and so on. Augmenting precision we may overcome algorithmic errors, but one does not know in advance how much this precision should be, and a trial-and-error approach is often the only way to follow. Coping with initial errors is an even more difficult task. In this experimental work we propose the combined use of syzygies and interval arithmetic to decide what to do at each critical point of the algorithm.
Published: Proceedings workshop CASC 2006. V.G. Ganzha, E.W. Mayr, E.V. Vorozhtsov ed. Springer-Verlag LNCS 4194. Chişinau, Moldova 2006, pp. 64-76, ISBN: 3-540-45182-X
Download: PDF-paper, PDF-slides, software.
Abstract: Karatsuba and Toom-Cook are well-known methods used to multiply efficiently two long integers. There have been different proposal about the interpolating values used to determine the matrix to be inverted and the sequence of operations to invert it. A definitive word about which is the optimal matrix (values) and the (number of) basic operations to invert it seems still not to have been said. In this paper we present some particular examples of useful matrices and a method to generate automatically, by means of optimised exhaustive searches on a graph, the best sequence of basic operations to invert them.
Published: Preprint N.605 Centro Interdipartimentale Vito Volterra - Università di Roma "Tor Vergata" (2006)
Download: PDF-paper, software.