| Computational Complexity Of Mathematical Operations |
Article Index for Computational |
Website Links For Computational |
Information AboutComputational Complexity Of Mathematical Operations |
| CATEGORIES ABOUT COMPUTATIONAL COMPLEXITY OF MATHEMATICAL OPERATIONS | |
| computational complexity theory | |
| arbitrary precision algorithms | |
| number theoretic algorithms | |
| mathematics-related lists | |
|
Here, complexity refers to the Time Complexity of performing computations on a Random Access Machine . See Big O Notation for an explanation of the notation used. ARITHMETIC AND ALGEBRAIC FUNCTIONS Schnorr and Stumpf C.P.Schnorr and G. Stumpf. A characterization of complexity sequences. Zeitschrift fur Mathematische Logik und Grundlagen der Mathematik 21(1):47--56, 1975. conjectured that no fastest algorithm for multiplication exists. SPECIAL FUNCTIONS The methods in this section are given in Borwein & Borwein.J. Borwein & P. Borwein. ''Pi and the AGM: A Study in Analytic Number Theory and Computational Complexity''. John Wiley 1987. Elementary functions The Elementary Function s are constructed by composing arithmetic operations, the Exponential Function (exp), the Natural Logarithm (log), Trigonometric Function s (sin, cos), and their inverses. The complexity of an elementary function is equivalent to that of its inverse, since all elementary functions are Analytic and hence invertible by means of Newton's method. In particular, if either exp or log can be computed with some complexity, then that complexity is attainable for all other elementary functions. Below, the size ''n'' refers to the number of digits of precision at which the function is to be evaluated. It is not known whether O((log ''n'') ''M''(''n'')) is the optimal complexity for elementary functions. The best known lower bound is the trivial bound O(''M''(''n'')). Non-elementary functions Mathematical constants This table gives the complexity of computing approximations to the given constants to ''n'' correct digits. NUMBER THEORY Algorithms for Number-theoretical calculations are studied in Computational Number Theory . MATRIX ALGEBRA The following complexity figures assume that arithmetic with individual elements has complexity O(1), as is the case with fixed-precision Floating-point Arithmetic . Henry Cohn , Robert Kleinberg , Balázs Szegedy and Christopher Umans show that either of two different conjectures would imply that the exponent of matrix multiplication is 2.Henry Cohn, Robert Kleinberg, Balazs Szegedy, and Chris Umans. Group-theoretic Algorithms for Matrix Multiplication. . ''Proceedings of the 46th Annual Symposium on Foundations of Computer Science'', 23-25 October 2005, Pittsburgh, PA, IEEE Computer Society, pp. 379–388. It has also been conjectured that no fastest algorithm for matrix multiplication exists, in light of the nearly 20 successive improvements leading to the Coppersmith-Winograd Algorithm . REFERENCES |
|
|