COMPUTATIONAL-COMPLEXITY OF SPARSE RATIONAL INTERPOLATION

被引：27

作者：

GRIGORIEV, D

KARPINSKI, M

SINGER, MF

机构：

[1] STEKLOV MATH INST, ST PETERSBURG 191011, RUSSIA

[2] INT COMP SCI INST, BERKELEY, CA 94720 USA

[3] N CAROLINA STATE UNIV, DEPT MATH, RALEIGH, NC 27695 USA

来源：

SIAM JOURNAL ON COMPUTING | 1994年 / 23卷 / 01期

关键词：

COMPUTATIONAL COMPLEXITY; INTERPOLATION; SPARSE RATIONAL FUNCTIONS; ARITHMETIC OPERATIONS;

D O I：

10.1137/S0097539791194069

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The authors analyze the computational complexity of sparse rational interpolation, and give the first deterministic algorithm for this problem with singly exponential bounds on the number of arithmetic operations.

引用

页码：1 / 11

页数：11

共 28 条

[1]

[Anonymous], 1977, BASIC ALGEBRAIC GEOM

[2]

[Anonymous], 1986, J SOVIET MATH, DOI DOI 10.1007/BF01095638

[3]

BENOR M, 1989, 20TH P ACM STOC, P301

[4]

BORODIN A, 1989, IBM RC14923 TJ WATS

[5]

CHISTOV AL, 1984, LECT NOTES COMPUT SC, V176, P17

[6]

CHISTOV AL, 1986, J SOVIET MATH, V34

[7] GENERALIZED VANDERMONDE DETERMINANTS AND ROOTS OF UNITY OF PRIME ORDER [J].

EVANS, RJ ;

ISAACS, IM .

PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 1976, 58 (JUL) :51-54

[8] PRECISE SEQUENTIAL AND PARALLEL COMPLEXITY-BOUNDS FOR QUANTIFIER ELIMINATION OVER ALGEBRAICALLY CLOSED FIELDS [J].

FITCHAS, N ;

GALLIGO, A ;

MORGENSTERN, J .

JOURNAL OF PURE AND APPLIED ALGEBRA, 1990, 67 (01) :1-14

[9] COMPLEXITY OF DECIDING TARSKI ALGEBRA [J].

GRIGOREV, DY .

JOURNAL OF SYMBOLIC COMPUTATION, 1988, 5 (1-2) :65-108

[10] SOLVING SYSTEMS OF POLYNOMIAL INEQUALITIES IN SUBEXPONENTIAL TIME [J].

GRIGOREV, DY ;

VOROBJOV, NN .

JOURNAL OF SYMBOLIC COMPUTATION, 1988, 5 (1-2) :37-64

← 1 2 3 →