Exact matrix computation by multiple P-adic arithmetic

Abstract

Most of the algorithms are assumed to use exact computation. But in practice, the machine floating point arithmetic is implemented on these algorithms which causes many problems. The existing method is to use a link list representing arbitrary size of integer or decimal numbers, which is extremely time consuming for a larger size matrixcalculation. This dissertation research is to focus on finding an effective way to do exact large matrix calculation. We built a finite P-adic number system and found a method to detect overflow. Based on this method and Dixon – Krishnamurthy’s theory we established Dixon – Krishnamurthy algorithm to implement finite P-adic number system on linear and nonlinear matrix calculation. Dixon – Krishnamurthy algorithm transfers the classic symbolic calculation into integer calculation, significantly improving the calculation efficiency. Furthermore, based on the multiple modulus rational system and finite P-adic number system, we constructed a Multiple P-adic Data Type. The multiple P-adic Data Type can easily transform the finite P-adic calculation process into parallel calculation process without modification on math algorithms. With enough independent CPU resources, the calculation time is significantly decreased. We developed a computational library based on Multiple P-adic Data Type and the object oriented program using C/C++. Computational algorithms have been developed using the data type for the calculation of matrix inverse, Lower Hessenberg form transformation, Wilkinson form transformation, Frobenius form transformation, post processing from all the transformations, reflexive general matrix inverse, Moore Penrose inverse, calculation of Laplace’s method for FTA (Fundamental Theorem of Algebra), Bézoutian formulation of the Resultant and etc. Furthermore, based on the properties of the Multiple P-adic Data Structure, we have developed an efficient proactive self – defense algorithm, which can detect and recover compromised computational data.