Efficiently computing many roots of a function

doi:10.1137/S1064827502406531

Efficiently computing many roots of a function

2005-01-01

5

PRE

AI

D

Dimitris J. Kavvadias *

DOI：10.1137/S1064827502406531

Original

Original request for help

Save

Abstract

En 中文

We present a new bisection based method for counting and computing roots of a function in a given interval. Our method is focused on very large problems, i.e., instances with the number of roots of the order of hundreds. The method draws its power from the fact that the roots are expected to be many, and is able to discover a large percentage of them very efficiently. Its main advantage, apart from its efficiency, is the fact that it requires only the sign of the function at a certain point and not its actual value. Also, its simplicity makes it a suitable preprocessing step for reducing the size of the problem, prior to more robust but also more demanding methods. The algorithm is accompanied by a probabilistic analysis of its behavior, which shows that a simple existence criterion like Bolzano's rule can be a powerful tool in the zero finding process.

Keywords:

zerofinding

expected behavior

bisection based methods

counting and computing the roots of a function

very large problems

Riemann's hypothesis

zeta-function

special functions

Elbert's conjecture

Efficiently computing many roots of a function

Abstract

AI Summary

Journal

Organization