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
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.
linear sparse systems; pade approximations; corank distribution
Full-text in one file
Для корректной работы сайта используйте один из современных браузеров. Например, Firefox 55, Chrome 60 или более новые.