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

Research output: Contribution to journal › Article › peer-review

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 2^pth roots of unity.

Original language	English
Pages (from-to)	792-802
Number of pages	11
Journal	Journal of Symbolic Computation
Volume	42
Issue number	8
DOIs	https://doi.org/10.1016/j.jsc.2007.04.004
Publication status	Published - 1 Jan 2007

Keywords

Algorithm
Computer algebra
FFT
Multiplication
Power series

Access to Document

10.1016/j.jsc.2007.04.004

Cite this

@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",

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

Abstract

Keywords

Access to Document

Fingerprint

Cite this