Optimized Computation for Determinant of Multivariate Polynomial Matrices on GPGPU

The determinant of the matrix is a fundamental concept in linear algebra and has various applications in research and engineering. Compared to the easy-calculating numeric matrix, a symbolic matrix with multivariate polynomial entries is hard to calculate because of immediate expression expansion, which often leads to drastic exhaustion of the physical memory. In this paper, we present a novel four-stage-approach to calculate the accurate determinant of multivariate polynomial matrices on GPGPU, through using the modular method, the Stockham Fast Fourier Transformation(FFT), the inverse FFT, and the Chinese Remainder Theorem. In our approach, the computation tasks in each stage are deployed on GPGPU so that the calculation could be recovered without loss at any point in case of inevitable interruptions happened during the parallel processing. In addition, to control the parallel computation time, we propose a time prediction model for the computation of polynomial determinant according to the basic matrix attributes. The experiment results show that our approach owns substantial speedups compared to Maple, allowing memory and time usage in steady increments.