New algorithms for relaxed multiplication

Joris van der Hoeven

doi:10.1016/j.jsc.2007.04.004

New algorithms for relaxed multiplication

Joris van der Hoeven

Résultats de recherche: Contribution à un journal › Article › Revue par des pairs

Résumé

In previous work, we have introduced the technique of relaxed power series computations. With this technique, it is possible to solve implicit equations almost as quickly as doing the operations which occur in the implicit equation. Here "almost as quickly" means that we need to pay a logarithmic overhead. In this paper, we will show how to reduce this logarithmic factor in the case when the constant ring has sufficiently many 2^pth roots of unity.

langue originale	Anglais
Pages (de - à)	792-802
Nombre de pages	11
journal	Journal of Symbolic Computation
Volume	42
Numéro de publication	8
Les DOIs	https://doi.org/10.1016/j.jsc.2007.04.004
état	Publié - 1 janv. 2007

Accès au document

10.1016/j.jsc.2007.04.004

Contient cette citation

@article{0272d5922c844c75bf4c1db7ee498c98,

title = "New algorithms for relaxed multiplication",

abstract = "In previous work, we have introduced the technique of relaxed power series computations. With this technique, it is possible to solve implicit equations almost as quickly as doing the operations which occur in the implicit equation. Here {"}almost as quickly{"} means that we need to pay a logarithmic overhead. In this paper, we will show how to reduce this logarithmic factor in the case when the constant ring has sufficiently many 2pth roots of unity.",

keywords = "Algorithm, Computer algebra, FFT, Multiplication, Power series",

author = "\{van der Hoeven\}, Joris",

year = "2007",

month = jan,

day = "1",

doi = "10.1016/j.jsc.2007.04.004",

language = "English",

volume = "42",

pages = "792--802",

journal = "Journal of Symbolic Computation",

issn = "0747-7171",

publisher = "Academic Press",

number = "8",

}

TY - JOUR

T1 - New algorithms for relaxed multiplication

AU - van der Hoeven, Joris

PY - 2007/1/1

Y1 - 2007/1/1

N2 - In previous work, we have introduced the technique of relaxed power series computations. With this technique, it is possible to solve implicit equations almost as quickly as doing the operations which occur in the implicit equation. Here "almost as quickly" means that we need to pay a logarithmic overhead. In this paper, we will show how to reduce this logarithmic factor in the case when the constant ring has sufficiently many 2pth roots of unity.

AB - In previous work, we have introduced the technique of relaxed power series computations. With this technique, it is possible to solve implicit equations almost as quickly as doing the operations which occur in the implicit equation. Here "almost as quickly" means that we need to pay a logarithmic overhead. In this paper, we will show how to reduce this logarithmic factor in the case when the constant ring has sufficiently many 2pth roots of unity.

KW - Algorithm

KW - Computer algebra

KW - FFT

KW - Multiplication

KW - Power series

U2 - 10.1016/j.jsc.2007.04.004

DO - 10.1016/j.jsc.2007.04.004

M3 - Article

AN - SCOPUS:34547200477

SN - 0747-7171

VL - 42

SP - 792

EP - 802

JO - Journal of Symbolic Computation

JF - Journal of Symbolic Computation

IS - 8

ER -

New algorithms for relaxed multiplication

Résumé

Accès au document

Empreinte digitale

Contient cette citation