Menu: Home :: go to Journal :: switch to Russian :: switch to English
You are here: all Journals and Issues→ Journal→ Issue→ Article

ESTIMATES OF THE RUNNING TIME AND MEMORY REQUIREMENTS OF THE NEW ALGORITHM OF SOLVING LARGE SPARSE LINEAR SYSTEMS OVER THE FIELD WITH TWO ELEMENTS

Annotation

A new algorithm of solving large sparse linear systems over field with two elements is considered in this work. Algorithm was proposed by M.A. Cherepniov. Algorithm uses the construction of matrix Pade approximations over finite fields. It is supposed that elements of approximation polynomials are independent and are identically distributed. Method for finding distributions of coranks of random symmetric, antisymmetric and common matrices is constructed. Lower and upper bounds for number of previous approximations sufficient to construct the next one are obtained. The logarithmic dependence for sufficient number of keeping approximations on every step for successful completion of algorithm with probability of 0.99 is found. Using the computer program exact values of estimates of running time and memory requirements are found, results are given in this work.

Keywords

linear sparse systems; pade approximations; corank distribution

Full-text in one file

Download

UDC

519.612

Pages

1311-1327

Для корректной работы сайта используйте один из современных браузеров. Например, Firefox 55, Chrome 60 или более новые.