The topic is quite extensive, there are a number of widely used storage schemes and many solution algorithms depending on specific goals. There are many literatures, but it will take a year to sort everything out, or even more than one. What is needed is speed optimization for a rather specific type of matrices and very limited actions with them. Maybe someone from here present understands this topic not by hearsay and can help navigate?

There are large matrices, sparse (less than 1% of non-zero elements), with a main diagonal, symmetrical, contain only 0 and 1, all very similar, images of examples: http://imgur.com/a/rYjIq

These are small, will be up to 150,000 orders. Similar to tapes, the solution of which comes down to seconds, but there is rubbish around, I don’t know if they can be brought to tape ones or is there no point and there are other methods for this problem? I need to come up with an algorithm for the program to solve them. So far, he has implemented solutions of the SLAE by the Gauss method, optimized for 64bit taking into account boolean variables (storage in the form of bits for faster multiplication and addition operations). The result is 50.041 x 50.041, which has 0.73% of non-zero elements, is solved in about 10 minutes, which is not correct and it is clear that you need to change the logic, and not optimize further. They told about sparse matrices and this topic is very suitable for my case, but I can not decide which algorithm is most suitable for my task in order not to try everything.

Closed due to the fact that the issue is too general for Kromster , cheops , user194374, Denis , aleksandr barakin participants 19 Jul '16 at 6:30 .

Please correct the question so that it describes the specific problem with sufficient detail to determine the appropriate answer. Do not ask a few questions at once. See “How to ask a good question?” For clarification. If the question can be reformulated according to the rules set out in the certificate , edit it .

  • 3
    Describe the task in detail immediately. So who wants to answer will not have to be noted in the comments and wait for you to add a question, and you will not get fair cons for writing something incomprehensible instead of a question. - Alexey Ukolov
  • And yet, a well-formulated question is half the answer. - Kromster
  • @ Alexey Ukolov, described - Isaev
  • It seems that it is easier to search libraries for your Intel MKL type language ... software.intel.com/en-us/node/520871 Well, you probably still have to read and understand ... - Yura Ivanov
  • one
    @Isaev, libraries can be sharpened for anything. Including sparse matrices. And in this case, the library solution is a universal one; a proven one would be preferable to a lame bicycle of its own. And if there are no such libraries for Delphi (who uses it in 2016 at all?), Then you should think about switching to the modern language. For example, python Googles everything perfectly over sparse matrices - en.wikipedia.org/wiki/Sparse_matrix and it makes no sense to reprint everything in response. - m9_psy

1 answer 1

  1. The fact that the matrix was initially filled with 0 and 1 after the first pass by the Gauss method will cease to work - you will get the usual numerical matrix. There is no sense in using special types.
  2. With such orders, the Gauss method will show the weather on Mars, it works up to 10,000.
  3. Use iterative methods like GMRES or conjugate gradients.
  4. What will this matter be considered? Person? Server? Cluster?

Start with the simplest = store arrays of pairs (index, value) for each row. For iterations, GMRES will be satisfactory.

  • 1. will not stop, will not work. For binary arithmetic is used the usual addition and multiplication are replaced by modulo 2 addition operations and processing 128 values ​​(MMX) in one operation ... (the answers are also only 0 or 1) as a result, even the reverse pass is not needed and as a result: the use of special types gives a very noticeable plus. 2. Yes, I have already noticed. 3. Thanks for the first practical advice. Conjugate gradients seemed more appropriate for my problem, but on a small number of GMRES processors will it be more efficient? 4. Target personalka, I can play around both on the server and on the cluster. - Isaev
  • Question after: How to parallelize an iterative algorithm? After all, by definition, at each iteration, it uses the result of the previous one, which means I cannot start the second thread until there is no result from the first ... - Isaev
  • 2
    @Isaev should have been written in huge letters in the question that you work within the framework of Boolean algebra. Look carefully at the formulation of the algorithm, that GMRES, that Gauss - and there and there is a step, where all the rows of the matrix must be either scalar multiplied by the next solution (GMRES) or added to the leading row (Gauss). From here and dance - we cut the matrix into horizontal tapes and give these tapes to the processor. - gbg