Evaluation properties of invariant polynomials

被引：1
作者：
Dahan, Xavier [1 ]
Schost, Eric [2 ]
Wu, Jie [2 ,3 ]
机构：
[1] Rikkyo Univ, Dept Math, Coll Sci, Tokyo 171, Japan
[2] Univ Western Ontario, Dept Comp Sci, London, ON, Canada
[3] Chinese Acad Sci, Grad Univ, Beijing, Peoples R China
来源：
JOURNAL OF SYMBOLIC COMPUTATION | 2009年 / 44卷 / 11期
基金：
加拿大自然科学与工程研究理事会;
关键词：
Invariant polynomial; Straight-line program; Complexity; Lifting techniques; STRAIGHT-LINE PROGRAMS; GROBNER BASES; ALGORITHMS; SYSTEM;
D O I：
10.1016/j.jsc.2008.12.002
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
A polynomial invariant under the action of a finite group can be rewritten using generators of the invariant ring. We investigate the complexity aspects of this rewriting process; we show that evaluation techniques enable one to reach a polynomial cost. (C) 2009 Elsevier Ltd. All rights reserved.
引用
收藏
页码：1592 / 1604
页数：13
相关论文
共 50 条
[21]   Specification Languages for Stutter-Invariant Regular Properties [J].
Dax, Christian ;
Klaedtke, Felix ;
Leue, Stefan .
AUTOMATED TECHNOLOGY FOR VERIFICATION AND ANALYSIS, PROCEEDINGS, 2009, 5799 :244-+
[22]   Computing and using minimal polynomials [J].
Abbott, John ;
Bigatti, Anna Maria ;
Palezzato, Elisa ;
Robbiano, Lorenzo .
JOURNAL OF SYMBOLIC COMPUTATION, 2020, 100 :137-163
[23]   Factoring sparse polynomials fast [J].
Demin, Alexander ;
van der Hoeven, Joris .
JOURNAL OF COMPLEXITY, 2025, 88
[24]   Efficient Evaluation of Matrix Polynomials beyond the Paterson-Stockmeyer Method [J].
Sastre, Jorge ;
Ibanez, Javier .
MATHEMATICS, 2021, 9 (14)
[25]   Efficient and stable numerical method for evaluation of Zernike polynomials and their Cartesian derivatives [J].
Novak, Pavel ;
Novak, Jiri .
MODELING ASPECTS IN OPTICAL METROLOGY IV, 2013, 8789
[26]   Interpolation by decomposable univariate polynomials [J].
von zur Gathen, Joachim ;
Matera, Guillermo .
JOURNAL OF COMPLEXITY, 2024, 85
[27]   On testing monomials in multivariate polynomials [J].
Chen, Zhixiang ;
Fu, Bin ;
Liu, Yang ;
Schweller, Robert .
THEORETICAL COMPUTER SCIENCE, 2013, 497 :39-54
[28]   Singularity-Free Evaluation of Collapsed-Coordinate Orthogonal Polynomials [J].
Kirby, Robert C. .
ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE, 2010, 37 (01)
[29]   Automatic invariant strengthening to prove properties in bounded model checking [J].
Awedh, Mohammad ;
Somenzi, Fabio .
43RD DESIGN AUTOMATION CONFERENCE, PROCEEDINGS 2006, 2006, :1073-+
[30]   Grobner bases of bihomogeneous ideals generated by polynomials of bidegree (1,1): Algorithms and complexity [J].
Faugere, Jean-Charles ;
El Din, Mohab Safey ;
Spaenlehauer, Pierre-Jean .
JOURNAL OF SYMBOLIC COMPUTATION, 2011, 46 (04) :406-437
12345