Algorithms For Determinant Calculation Of Dense Matrix With Multivariate Polynomial Entries In Many-Core Environment

In recent years,a lot of many-core devices such as GPGPU has already used in the research of highly concurrent and massively scientific computing algorithm,providing accurate result in a predictable time,which saves a lot of time and space when comparing to the traditional methods.Based on the theory in the field of symbolic computation,this dissertation provides a fast and accuracy determinant calculation method for dense matrix with multivariate polynomial entries under many-core environment,using GPGPU and modular method.The details are as follows.First,we separate the problem into sub-problems in finite field and recover all the results with CRT,which ensures the calculation with large integers in a massive scale ac-curately.Second,we design the multi-FFT algorithm to replace the symbolic computation into numerical computation using GPGPU and the memory never swells during the pro-cess any more.Moreover,we provide a fast and accuracy determinant calculation method for massive integer matrix using GPGPU.Our method eliminates the error caused by float-ing point calculation,and calculates in a massive scale accurately.Finally,we collect all the sub-answers and recover the answer of the original matrix by CRT using GPGPU.The experiments indicate that our method takes less time and memory when compar-ing to other well-known mathematical packages,especially when computing the determi-nant with high matrix order.In addition,the memory never swells during the calculation and it is a growing advantage when the order increase.We also analyze the method in a theoretical way.Comparing to the traditional methods,the determinant is calculated over the finite field using modular method,which ensures that we can get the exact answer in a finite time.Moreover,the multiplication of the primes which are 9 bits in 32 word size is about 1O9000,indicating that our method can afford the ordinary computation in both the field of scientific research and engineering application.