Polynomial matrices and ideals generated by their minors appear in various domains such as cryptography, polynomial optimization and effective algebraic geometry. When the given matrix is symmetric, this additional structure on top of the determinantal structure, affects computations on the derived ideals. Thus, understanding the complexity of these computations is important. Moreover, this study serves as a stepping stone towards further understanding the effects of structure in determinantal systems, such as those coming from moment matrices. In this paper, we focus on the Sparse-FGLM algorithm, the state-of-the-art for changing ordering of Gröbner bases of zero-dimensional ideals. Under a variant of Fröberg's conjecture, we study its complexity for symmetric determinantal ideals and identify the gain of exploiting sparsity in the Sparse-FGLM algorithm compared with the classical FGLM algorithm. For an n×n symmetric matrix with polynomial entries of degree d, we show that the complexity of Sparse-FGLM for zero-dimensional determinantal ideals obtained from this matrix over that of the FGLM algorithm is at least O(1/d). Moreover, for some specific sizes of minors, we prove finer results of at least O(1/nd) and O(1/m3d).

Quantifier elimination over the reals is a central problem in computational real algebraic geometry, polynomial system solving and symbolic computation. Given a semi-algebraic formula (whose atoms are polynomial constraints) with quantifiers on some variables, it consists in computing a logically equivalent formula involving only unquantified variables. When there is no alternation of quantifiers, one has a one block quantifier elimination problem.

Let R be the field of real numbers. We consider the problem of computing the real isolated points of a real algebraic set in Rn given as the vanishing set of a polynomial system. This problem plays an important role for studying rigidity properties of mechanism in material designs. In this paper, we design an algorithm which solves this problem. It is based on the computations of critical points as well as roadmaps for answering connectivity queries in real algebraic sets. This leads to a probabilistic algorithm of complexity (nd)O (n log(n)) for computing the real isolated points of real algebraic hypersurfaces of degree d. It allows us to solve in practice instances which are out of reach of the state-of-the-art.

For genetic algorithms (GAs) using a bit-string representation of length n, the general recommendation is to take 1/n as mutation rate. In this work, we discuss whether this is justified for multi-modal functions. Taking jump functions and the (1+1) evolutionary algorithm (EA) as the simplest example, we observe that larger mutation rates give significantly better runtimes. For the Jumpm, n function, any mutation rate between 2/n and m/n leads to a speedup at least exponential in m compared to the standard choice.