Complexity bounds for zero-test algorithms

Joris van der Hoeven; John Shackell

doi:10.1016/j.jsc.2006.06.001

Complexity bounds for zero-test algorithms

Joris van der Hoeven
, John Shackell

Université Paris-Saclay
University of Kent

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

8 Citations (Scopus)

Abstract

In this paper, we analyze the complexity of a zero-test for expressions built from formal power series solutions of first order differential equations with non-degenerate initial conditions. We will prove a doubly exponential complexity bound. This bound establishes a power series analogue for "witness conjectures".

Original language	English
Pages (from-to)	1004-1020
Number of pages	17
Journal	Journal of Symbolic Computation
Volume	41
Issue number	9
DOIs	https://doi.org/10.1016/j.jsc.2006.06.001
Publication status	Published - 1 Jan 2006
Externally published	Yes

Keywords

Complexity
Pfaffian series
Power series
Witness conjecture
Zero-test

Access to Document

10.1016/j.jsc.2006.06.001

Cite this

@article{7ff39bc225564864b057a7c67f575dc6,

title = "Complexity bounds for zero-test algorithms",

abstract = "In this paper, we analyze the complexity of a zero-test for expressions built from formal power series solutions of first order differential equations with non-degenerate initial conditions. We will prove a doubly exponential complexity bound. This bound establishes a power series analogue for {"}witness conjectures{"}.",

keywords = "Complexity, Pfaffian series, Power series, Witness conjecture, Zero-test",

author = "\{van der Hoeven\}, Joris and John Shackell",

year = "2006",

month = jan,

day = "1",

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

language = "English",

volume = "41",

pages = "1004--1020",

journal = "Journal of Symbolic Computation",

issn = "0747-7171",

publisher = "Academic Press",

number = "9",

}

TY - JOUR

T1 - Complexity bounds for zero-test algorithms

AU - van der Hoeven, Joris

AU - Shackell, John

PY - 2006/1/1

Y1 - 2006/1/1

N2 - In this paper, we analyze the complexity of a zero-test for expressions built from formal power series solutions of first order differential equations with non-degenerate initial conditions. We will prove a doubly exponential complexity bound. This bound establishes a power series analogue for "witness conjectures".

AB - In this paper, we analyze the complexity of a zero-test for expressions built from formal power series solutions of first order differential equations with non-degenerate initial conditions. We will prove a doubly exponential complexity bound. This bound establishes a power series analogue for "witness conjectures".

KW - Complexity

KW - Pfaffian series

KW - Power series

KW - Witness conjecture

KW - Zero-test

U2 - 10.1016/j.jsc.2006.06.001

DO - 10.1016/j.jsc.2006.06.001

M3 - Article

AN - SCOPUS:33746912038

SN - 0747-7171

VL - 41

SP - 1004

EP - 1020

JO - Journal of Symbolic Computation

JF - Journal of Symbolic Computation

IS - 9

ER -

Complexity bounds for zero-test algorithms

Abstract

Keywords

Access to Document

Fingerprint

Cite this