Teaching Students to Use the Gauss Method for Integer Matrices  when Implemented on a Computer

Tatiana M. Kosovskaya

doi:10.32603/2071-2340-2019-3-90-95

Tatiana M. Kosovskaya Saint Petersburg State University, 28 Universitetskiy pr., Stary Peterhof, 198504, Saint Petersburg, Russia

DOI: https://doi.org/10.32603/2071-2340-2019-3-90-95

Keywords: Gauss method, computational complexity, computation with large integers

Abstract

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.

Author Biography

Tatiana M. Kosovskaya, Saint Petersburg State University, 28 Universitetskiy pr., Stary Peterhof, 198504, Saint Petersburg, Russia

Doctor of physical and mathematical Sciences, associate Professor, Professor of the Department of Informatics of the faculty of mathematics and mechanics of Saint Petersburg state University, kosovtm@gmail.com

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).