Claus Fieker . Jayantha Suranimalee

University of Kaiserslautern, Germany, Email: eker@mathematik.uni-kl.de, Department of Mathematics, University of Colombo, Sri Lanka Email: surani- malee@maths.cmb.ac.lk

Received in final form on January 22, 2022

Abstract
In this paper, we present a deterministic algorithm for solving a non-square linear system over rationals and number fields. When the solution is not unique, we compute a basis for the kernel to normalize the solution. In this computation, we use a modified version of Dixon's algorithm. We rigorously assess its complexity as O~(m3d2 + m2nd + m2d5) operations over Z, whereas the Gaussian method takes O~(m3n2d2) operations to solve a linear mxn system Ax = b over number field K of degree d.

Keywords
Non-square linear system, kernel, Dixon's algorithm

Cite This Article
Claus Fieker and Jayantha Suranimalee, Fast and Practical Algorithms for Solving Non-square Linear Systems, J. Innovation Sciences and Sustainable Technologies, 2(1)(2022), 25-31. https://doie.org/10.0608/JISST.2022433697

    119    3    Download