Linear Algebra over Finitely Generated Fields and Rings

  • Linear algebra, together with polynomial arithmetic, is the foundation of computer algebra. The algorithms have improved over the last 20 years, and the current state of the art algorithms for matrix inverse, solution of a linear system and determinants have a theoretical sub-cubic complexity. This thesis presents fast and practical algorithms for some classical problems in linear algebra over number fields and polynomial rings. Here, a number field is a finite extension of the field of rational numbers, and the polynomial rings we considered in this thesis are over finite fields. One of the key problems of symbolic computation is intermediate coefficient swell: the bit length of intermediate results can grow during the computation compared to those in the input and output. The standard strategy to overcome this is not to compute the number directly but to compute it modulo some other numbers, using either the Chinese remainder theorem (CRT) or a variation of Newton-Hensel lifting. Often, the final step of these algorithms is combined with reconstruction methods such as rational reconstruction to convert the integral result into the rational solution. Here, we present reconstruction methods over number fields with a fast and simple vector-reconstruction algorithm. The state of the art method for computing the determinant over integers is due to Storjohann. When generalizing his method over number field, we encountered the problem that modules generated by the rows of a matrix over number fields are in general not free, thus Strojohann's method cannot be used directly. Therefore, we have used the theory of pseudo-matrices to overcome this problem. As a sub-problem of this application, we generalized a unimodular certification method for pseudo-matrices: similar to the integer case, we check whether the determinant of the given pseudo matrix is a unit by testing the integrality of the corresponding dual module using higher-order lifting. One of the main algorithms in linear algebra is the Dixon solver for linear system solving due to Dixon. Traditionally this algorithm is used only for square systems having a unique solution. Here we generalized Dixon algorithm for non-square linear system solving. As the solution is not unique, we have used a basis of the kernel to normalize the solution. The implementation is accompanied by a fast kernel computation algorithm that also extends to compute the reduced-row-echelon form of a matrix over integers and number fields. The fast implementations for computing the characteristic polynomial and minimal polynomial over number fields use the CRT-based modular approach. Finally, we extended Storjohann's determinant computation algorithm over polynomial ring over finite fields, with its sub-algorithms for reconstructions and unimodular certification. In this case, we face the problem of intermediate degree swell. To avoid this phenomenon, we used higher-order lifting techniques in the unimodular certification algorithm. We have successfully used the half-gcd approach to optimize the rational polynomial reconstruction.

Download full text files

Export metadata

Metadaten
Author:Mannaperuma Herath Mudiyanselage Jayantha Suranimalee
URN:urn:nbn:de:hbz:386-kluedo-65606
DOI:https://doi.org/10.26204/KLUEDO/6560
Advisor:Claus Fieker
Document Type:Doctoral Thesis
Language of publication:English
Date of Publication (online):2021/09/09
Year of first Publication:2021
Publishing Institution:Technische Universität Kaiserslautern
Granting Institution:Technische Universität Kaiserslautern
Acceptance Date of the Thesis:2021/04/29
Date of the Publication (Server):2021/09/09
Tag:characteristic polynomial; determinant; kernel; minimal polynomial; non square linear system solving; reconstructions; unimodular certification
GND Keyword:determinant; kernel; linear systems; characteristic polynomial; minimal polynomial; reconstructions; number fields; unimodularity
Page Number:XII, 120
Faculties / Organisational entities:Kaiserslautern - Fachbereich Mathematik
DDC-Cassification:5 Naturwissenschaften und Mathematik / 510 Mathematik
MSC-Classification (mathematics):11-XX NUMBER THEORY
15-XX LINEAR AND MULTILINEAR ALGEBRA; MATRIX THEORY
Licence (German):Creative Commons 4.0 - Namensnennung, nicht kommerziell, keine Bearbeitung (CC BY-NC-ND 4.0)