|
|
 |
| Авторизация |
|
|
|
| Поиск по указателям |
|
|
|
|
|
|
|
 |
|
|
|
| Burgisser P., Clausen M., Shokrollahi M.A. — Algebraic complexity theory |
|
|
|
| Предметный указатель |
Frobenius reciprocity theorem 335
Fundamental theorem of algebra 286
Gauss lemma 172
GCD see "Greatest common divisor"
Generalized null algebra see "Null algebra"
Generating polynomial of a sequence 92 450
Generic computation 208
Generic path 123
Generic Vandermonde matrix 318
Generic width 281
Geometric constructions by ruler and compass 280
Geometric degree of a variety 179
Geometric degree, lower bound by 185
Geometric Goppa codes 502
Gradient, lower bound by 165 285
Graph, associated to a straight-line program 105
Greatest common divisor see "Euclidean algorithm" "Euclidean
Greatest common divisor for multivariate polynomials 98
Greatest common divisor of integer polynomials 98
Group algebra 327
Group nilpotent 339
Group solvable 339
Group supersolvable 339
Group symmetric 342
Hamiltonian cycle polynomials 547
Hamiltonian cycle problem 547
Hamming metric, sphere, weight 489
Hankel matrix 311
Hasse — Weil theorem 501
Height 212
Hensel lifting 98
Hermite interpolation 79 94 205
Hilbert function 178
Hilbert polynomial 179
Hilbert — Serre theorem 178
Homogeneous straight-line program 551
Horner’s rule 5 125 144
Horner’s rule, optimality of 147 285
Huffman coding 43 55 61 75
Huffman tree 40
Immanent 575
Indecomposable tensor 372
Initial segment of a binary tree 114
Inner product 158
Input 105
Input generic 118
Input isomorphic 106
Input set belonging to a node 119
Input universal 106
Instruction 105 115
Instruction parametric 139
Integer linear programming 84
Integral operator 57
Interpolation 29 53 75—79 94
Interpolation Hermite 94 205
Interpolation on algebraic curves 497
Interpolation, lower bound for 187
Intersection multiplicities 179
Inv problem sequence 427
Inversion of  -matrices 159
Inversion of a general polynomial 55
Inversion of complex numbers 159
Inversion of power series 44
Irreducible component 122
Irreducible representation 329
Irreducible topological space 122
Irrelevant ideals 178
Isotropy group 484
Isotypic component 337
Isotypic decomposition 337
Iteration procedures 206
Jensen’s Inequality 54
Join of homogeneous ideals 201
Join of projective varieties 201
Jordan block 506
k-algebra 356
K-DAG over (n, m) 314
K-DAG standard 315
K-DAG, depth of 318
Karatsuba algorithm 53
Ker problem sequence 439
Knapsack problem 83 276 278
Knuth — Schoenhage algorithm 61—74
Knuth — Schoenhage algorithm, local analysis of 71
Kronecker product 11
Kummer extension 222
Kusnirenko’s conjecture 301
Lagrange interpolation formula 77
Language 543
Laplace expansion theorem 559
Largest empty circle problem 276
Laser method 391—407
Left module for a group algebra 328
Left-kernel of a bilinear map 363
Left-kernel of a quadratic map 457
LFL-complexity 573
LFL-program 572
Lie algebra 488
Lie algebra sl(2,k) 518
Linear complexity 307
Linear complexity of a finite group 328
Linear complexity of specific matrices 236
Linear complexity, c-restricted 312
Linear computation graph see "K-DAG"
Linear computation sequence 307
Linear decision complexity 283
Linear decision tree 94 95
Linear disjointness 134
Linear representation of a group 328
Linear space of a divisor 497
Linear straight-line program 306
Linear transformation of a bilinear computation 477
Linearly generated sequence 92 450
Local ring of a point 161
Localization of k[X] 165
Locally closed subset 123
Lower bound by Betti numbers 283 284
Lower bound by degree of linearization 149
Lower bound by degree of Zeta function 286
Lower bound by Euler characteristic 284
Lower bound by facets of a polytope 280
Lower bound by generic width 281
Lower bound by geometric degree 185
Lower bound by gradient 165 285
Lower bound by number of connected components 272 299
Lower bound by number of faces 282
Lower bound by number of real roots 296
Lower bound by Schwarz genus 286
Lower bound by substitution method 149 285
Lower bound by transcendence degree 131 135 285
Lower semicontinuous 526
LUP problem sequence 428
LUP-Decomposition 428
MaMu problem sequence 425
Maschke’s Theorem 333 346
Matrix inversion, complexity of 166 430
Matrix multiplication 10—14 356
Matrix multiplication, asymptotic complexity see "Exponent of matrix multiplication"
Matrix multiplication, complexity (rank) for special formats 371
Matrix multiplication, complexity (rank) for special formats 10—13 412 459 462
Matrix multiplication, complexity (rank) for special formats  371 413
Matrix multiplication, complexity (rank) for special formats, rectangular 411 422
Matrix multiplication, lower bound 459 460
Matrix multiplication, lower bound over  496 501
Matrix multiplication, partial 407—410 419
Matrix multiplication, verification of 452
Matrix representation 328
Matrix times vector 149 158
Maximum, computation of 281
Measure problem 278
| Membership problem 117 247 272
Membership problem, integer constrained form 286
Menger’s theorem 322
Mergesort algorithm 121
Milnor — Thom bound 270
Minimal border rank 419
Minimal field of definition 285
Minimal rank 474
Minimum polynomial of a sequence 92 450
Moebius transformation 299
Monomially equivalent 338
Morse — Sard theorem 293
Morse — Sard theorem, semi-algebraic 267
Multiple evaluation 77 173
Multiplication of complex numbers 159
Multiplication of polynomials 29 33 35
Multiplication of power series 44
Multiplication of several polynomials 40 43 188
Multiplication of sparse polynomials 371
Multiplicative branching complexity 118 272
Multiplicative complexity 108 110 118
Multiplicative complexity of a quadratic map 352
Multiplicative complexity of an algebra 356
Multiplicity of representations 333
Nash function 282
Nash m-comer point 282
Network theory 349
Newton iteration 49 56
Newton relation 46
Newton step 159
Nick’s class  568
Non-degenerate solution 266 289
Noncommutative algorithm 373
Nonscalar complexity 28 108 124
Nonscalar cost 28
Null algebra 474
Null tensor 368
OgB problem sequence 441
Orthogonal basis transform 441
Ostrowski model 6
Output class 116
p-bounded 544
p-Computable 545
P-equivalent 546
p-Expressible 550
p-Family 545
p-Projection 547
Pade approximation 62 92 99
Parallel algorithms 59
Partial fraction 139 141
Partial matrix multiplication see "Matrix multiplication"
Partition of a natural number 342
Partition of inputs of a tree 117
Pencil 505 523 535
Pencil, canonical forms of 507
Pencil, elementary divisors of 506
Pencil, equivalent 505
Pencil, Frobenius companion block 506
Pencil, invariant divisors of 506
Pencil, Jordan block 506
Pencil, minimal column index of 508
Pencil, minimal row index of 508
Pencil, rank of 508
Pencil, regular kernel of 507
Pencil, singular 506
Pencil, Weierstrass — Kronecker canonical form of 507
Permanent family 20 548
Permanent, Ryser’s formula for 569
Permutation of a bilinear computation 477
Places of an AF1 497
Point location 79
Polynomial multiplication see "Multiplication of polynomials"
Polynomially, bounded function 544
Polynomially, reducible 546
Polynomially, related complexity measures 545
Polynomials with 0, 1-coefficients 221 239 243
Polynomials with algebraic coefficients 218—224
Polynomials with integer roots 243
Polynomials with rapidly growing coefficients 224—230 240
Polynomials, easy to compute 221
Polytope 80
Power sum 174
Powering of power series 51
PowerSUM 46 285
Preconditioning 126 128 144 145
Prime number theorem 210 242
Probabilistic computation tree 286
Problem 425
Problem sequence, 3-Cpr 448
Problem sequence, CharPol 435
Problem sequence, Det 430
Problem sequence, Ech 432
Problem sequence, exponent of 426
Problem sequence, Inv 427 430
Problem sequence, Ker 439
Problem sequence, LUP 428
Problem sequence, OgB 441
Problem sequence, RNF 435
Problem sequence, SLS 451
Problem sequence, Spr 449
Problem sequence, TInv 427
Product tree 40
Projection 547
Projective linear subspace 179
Projective variety 178
Proper map 293
q-ary entropy function 500
qp-Bounded 562
qp-Computable 562
qp-Expressible 562
qp-Projection 568
QR-decomposition 453
Quadratic algorithm see "Quadratic computation"
Quadratic computation 353
Quadratic form 352
Quadratic map 352
Quasi-polynomially bounded function 562
Quaternions see "Real quaternions"
Quotient 31
Quotient of a bilinear map 464
Quotient of general polynomials 154
Radical of an algebra 466
Random access machine 124
Randomization 286
Range space 84
Rank and scalar extension 414
Rank maximal 523
Rank normal form 435
Rank of a bilinear map 354
Rank of a pencil 508
Rank of a tensor 358
Rank of an algebra 356 455—488
Rank of finite fields 497—498
Rank of specific tensors 237
Rank typical 522
Real quaternions, complexity of 472
Reciprocal of a polynomial 92
Regular point, value 293
Regular representation 347
Relative degree bound 185
Relative interior 80
Remainder 31
Representation of a finite group 328
Representation space 328
Representation theorem 212 242
Representation,  -adapted 333
Representation, induced 335
Representation, monomial 335
Representation, multiplicity-free 333
Residual subset 293
|
|
|
| Реклама |
|
|
|
|
|
О проекте