Teaching Students to Use the Gauss Method for Integer Matrices when Implemented on a Computer
DOI:
https://doi.org/10.32603/2071-2340-2019-3-90-95Keywords:
Gauss method, computational complexity, computation with large integersAbstract
The paper is written on the basis of a part of “Analysis of algorithms” course for students of the Computer science department of the Division of mathematics and mechanics of Saint Petersburg State University. The example of the computer implementation of the Gauss method illustrates the difference between the algebraic complexity (the number of arithmetic operations) of processing integers and the computational complexity which depends on the length of the input data. A formula which specifies the increase in the length of matrix coefficients, along with the implementation the Gauss method, is proved.
The problems arising in the processing of large integers associated with “chopping” numbers are shown. To overcome the indicated problems, the possibility of using multi-valued integers is proposed. The upper bounds of the number of steps for processing the multivalued integers is shown to coincide with such bounds for a multi-tape Turing machine.
References
T. M. Kosovskaya and N. K. Kosovskii, “About polynomial algorithms for solution of diophantine systems of linear equations and comparisons,” in Proc. of VIII International seminar Descrete mathematics and its applications, Moscow, 2004, pp. 72–74 (in Russian).
A. Schrijver, Theory of linear and integer programming, Wiley, 1998.
M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, New York: Freeman, 1979.
S. M. Okulov, Programming in algorithms, Moscow: BINOM, 2007 (in Russian).
Downloads
Published
Issue
Section
License
This work is licensed under a Creative Commons Attribution 4.0 International License.
