Efficient decomposition of separable algebras

摘要

We present new, efficient algorithms for computations on separable matrix algebras over infinite fields. We provide a probabilistic method of the Monte Carlo type to find a generator for the center of a given algebra U is contained in F~(m x m) over an infinite field F. The number of operations used is within a logarithmic factor of the cost of solving m x m systems of linear equations. A Las Vegas algorithm is also provided under the assumption that a basis and set of generators for the given algebra are available. These new techniques yield a partial factorization of the minimal polynomial of the generator that is computed, which may reduce the cost of computing simple components of the algebra in some cases.