1

Topic: How fast matrix multiplication accelerates calculation of Slough?

There is a so-called "school" method of the decision of linear equation systems - at first lead system to a triangular type, and then we calculate values of variables, we go reversely and is substituted already calculated to receive the remaining. About it is called as a method of the Gauss. Well or the same with selection of a principal/basic element. To me it is not clear - at what here multiplication of matrixes? How it is necessary to use fast matrix multiplication (which calculation of Slough can accelerate)?

2

Re: How fast matrix multiplication accelerates calculation of Slough?

Hello, Ejnstok Fajr, you wrote: > To me it is not clear - at what here multiplication of matrixes? > How it is necessary to use fast matrix multiplication (which calculation of Slough can accelerate)? And unless a method of the Gauss someone Slough solves? Whence at you such ?

3

Re: How fast matrix multiplication accelerates calculation of Slough?

N> And unless a method of the Gauss someone Slough solves? Whence at you such ? From school, and still here it is written - https://ru.wikipedia.org/wiki/%D0%9A%D0 … 0%90%D0%A3 And how solve actually?

4

Re: How fast matrix multiplication accelerates calculation of Slough?

Hello, Ejnstok Fajr, you wrote: > from school, and still here it is written - https://ru.wikipedia.org/wiki/%D0%9A%D0 … 0%90%D0%A3 Well, at the decision to writing-books, fast matrix multiplication explicitly is not necessary. In Wikipedia of simply link to methods. In a reality the method of the Gauss turns out one of the slowest. > And how solve actually? Somehow, depends on a situation: the size of matrixes, sparsity, how much exact decision it is necessary It is necessary to receive etc. to start with the task, rather the reverse.

5

Re: How fast matrix multiplication accelerates calculation of Slough?

N> depends on a situation: the size of matrixes, sparsity, how much exact decision it is necessary It is necessary to receive etc. to start with the task, rather the reverse. The size of matrixes big (for the manual account certainly, for you it can small) - the order of 10^5 equations,  high. The decision is necessary exact.

6

Re: How fast matrix multiplication accelerates calculation of Slough?

Hello, Ejnstok Fajr, you wrote: > the Size of matrixes big (for the manual account certainly, for you it can small) - the order of 10^5 equations,  high. The decision is necessary exact. And variables how many? A matrix redefined or not? I think that you should apply any expansion of a matrix. QR or SVD.

7

Re: How fast matrix multiplication accelerates calculation of Slough?

N> And variables how many? A matrix redefined or not? As much, a matrix square and it is exact not .

8

Re: How fast matrix multiplication accelerates calculation of Slough?

N> QR I do not understand, how QR can be faster. At first, it not exact, but iterated. Secondly, In this crude form the iterations are relatively expensive. This can be mitigated by first bringing the matrix A to upper Hessenberg form (which costs 10/3*n^3 + O (n^2) arithmetic operations using a technique based on Householder reduction) it 10/3*n^3 already more than n^3/4 at the Gauss...

9

Re: How fast matrix multiplication accelerates calculation of Slough?

Hello, Ejnstok Fajr, you wrote: > It 10/3*n^3 already more than n^3/4 at the Gauss... And what for to you QR if the system nondegenerate also has the unambiguous decision? You will receive exact values only in character arithmetics. I doubt that it is necessary to you.

10

Re: How fast matrix multiplication accelerates calculation of Slough?

N> you will receive Exact values only in character arithmetics. I can use https://en.wikipedia.org/wiki/Bareiss_algorithm It guarantees O (n^5) and any character arithmetics Initial coefficients at me all whole

11

Re: How fast matrix multiplication accelerates calculation of Slough?

N> what for to you QR if the system nondegenerate also has the unambiguous decision? Whence I know? You offered it! I only wanted more effective algorithm, than the Gauss. Speak that they are, but I do not understand as.

12

Re: How fast matrix multiplication accelerates calculation of Slough?

Hello, Ejnstok Fajr, you wrote: > To me it is not clear - at what here multiplication of matrixes? Thus that LU factorization - the advanced variant of algorithm of the Gauss c pivoting, having the same computing complexity. Rather  (a square against a cube of the size of system) we receive the decision of many systems with an identical left part. Minuses (that for the Gauss with swaps that for LU expansions) - are not present stability (even in a case with swaps) - are not present the registration of specific structure at a matrix in the left part. For example, if it Hermite it is necessary Holetsky to use factorization - is more computing more effectively and more stablly.