Hello. Studying sparse matrices (for which most of the elements are not 0, but let's say x, and which are organized as a list of trinary elements consisting of two indices and a value), it is easy enough to choose an algorithm for multiplying two matrices and calculate its complexity, which will be about (n ^ 3) with n * n matrices, if x = 0. In my analysis, the same efficiency can be achieved when x! = 0, but the algorithm will be much more difficult. The meaning is approximately the same, we cyclically get a row, for each row we get each column, but the complexity of the algorithm itself depends on how we work with those columns and rows that are either completely filled with the value of x or partially, that is, you can individually count the number of elements that will give x ^ 2 and add them to the current amount (new element in place i, j), also individually count the product of x and real values ​​either along the row or along the column until we reach the index where there are both real values , the product of which you need to add to the calculated amount.

that is, the sum formula for k from 0 to n (i, k) * (k, j) becomes non-linear.

Has anyone understood about the algorithm that I estimated? I can't even write an approximate pseudocode of it.

Can anyone know good sources on this topic, or can throw this algorithm in the simplest form here?

    1 answer 1

    Did I understand the algorithm? not.

    Studying sparse matrices (for which most of the elements are not 0, but let's say x , and which ... which will be about (n ^ 3) with n * n matrices, if x = 0

    Kind of weird. Not 0, but with equal 0 ... With equal 0 elements, the complexity is exactly O(n^2) - write n^2 zeros.

    Yes, and O(n^3) is for the product of any (not sparse) matrices when using the classical multiplication scheme ...

    And to read something classic (albeit ancient): Pissanecky S. Technology of sparse matrixes can be found on the Internet. There is also such a Matrix Template Library, you can look at it, but this is a very professional code, it’s just there that you don’t have to figure it out.