1

Topic: The effective decision big incompatible Slough

Kind time of days! There is certainly incompatible Slough (the order of 10000 variables and 40000 equations) for which it is necessary to search for the decision in sense of minimization of a discrepancy. System strongly rarefied - in each equation 1 or 2 variable, and remaining coefficients certainly zero. At a model development cycle in matlab for the decision of this task function mldivide which fulfilled less than for 0,1 was used. At a model rewriting on With ++ with Intel MKL usage the given code location began to be fulfilled ~10-50 seconds how I implemented it. If through direct usage QR of the solver (LAPACKE_dgels) on the dense matrix in the size 10*40 elements it turned out seconds 50 and a lot of storage on storage of all matrix (much more than consumed matlab). If through conversion to a type (A ^ {T} A) x = (A ^ {T} b) and search of the decision of this joint system (with the dense square matrix 10*10) with the help mkl_dcsrmv, mkl_dcsrmultd for conversion and LAPACKE_dgesv it is immediate for the decision I managed to receive time of the order of 10 seconds for the decision. It turns out that the difference in time with matlab - a minimum 2 orders that somehow is too much. Moreover, matlab in the virtual machine on 4-hletnem  CPU, and Intel MKL on new server Xeon E5 v4 generally was launched. Prompt, please, that I can do not so? Can be eat the implemented methods of the fast decision of such strongly rarefied incompatible Sloughs about which I do not know and about which it is not told in the function description mldivide (where generally it is said, what for my case is used QR the solver)?

2

Re: The effective decision big incompatible Slough

Hello, phprus, you wrote: P> Prompt, please, that I can do not so? It is necessary to profile. Frequent enough errors - the data  too  or on everyone  the heap when from the abstract layers is caused P> Can be eat the implemented methods of the fast decision of such strongly rarefied incompatible Sloughs about which I do not know and about which is not told in the function description mldivide (where generally it is said, what for my case is used QR the solver)? SSOR at colleagues well itself recommended. But depends on a matrix, it is how much good  .

3

Re: The effective decision big incompatible Slough

Hello, denisko, you wrote: P>> Prompt, please, that I can do not so? D> it is necessary to Profile. D> frequent enough errors - the data  too  or on everyone  the heap when from the abstract layers is caused All time spent inside MKL (even in one function - LAPACKE_dgels or LAPACKE_dgesv depending on a variant). The share of my code in the general time is insignificant. The dense matrixes in API MKL it is simple the unit of the continuous storage. Any abstractions here are impossible even theoretically. On the other hand matlab unambiguously uses rarefied storage for on all task less gigabyte of storage suffices it, and for storage of the dense matrix 10*40 in double it is required more than 3 Gb. P>> Can be eat the implemented methods of the fast decision of such strongly rarefied incompatible Sloughs about which I do not know and about which it is not told in the function description mldivide (where generally it is said, what for my case is used QR the solver)? D> SSOR at colleagues well itself recommended. But depends on a matrix, it is how much good  . I can not understand, and how it helps for the task where Slough certainly it is not joint? That I know all about initial system I described in the first message. Other convergence at me is not present. It is under construction depending on the exterior data.

4

Re: The effective decision big incompatible Slough

Hello, phprus, you wrote: P> Hello, denisko, you wrote: P>>> Prompt, please, that I can do not so? D>> it is necessary to Profile. D>> frequent enough errors - the data  too  or on everyone  the heap when from the abstract layers is caused P> All time spent inside MKL (even in one function - LAPACKE_dgels or LAPACKE_dgesv depending on a variant). The share of my code in the general time is insignificant. P> the dense matrixes in API MKL it is simple the unit of the continuous storage. Any abstractions here are impossible even theoretically. P> on the other hand matlab unambiguously uses rarefied storage for on all task less gigabyte of storage suffices it, and for storage of the dense matrix 10*40 in double it is required more than 3 Gb. I.e. you try to transform a disperse matrix to dense and then to solve methods for the dense? Well then it is absolutely bad way. Try from eigen  solvers. P>>> Can be eat the implemented methods of the fast decision of such strongly rarefied incompatible Sloughs about which I do not know and about which it is not told in the function description mldivide (where generally it is said, what for my case is used QR the solver)? D>> SSOR at colleagues well itself recommended. But depends on a matrix, it is how much good  . P> I can not understand, and how it helps for the task where Slough certainly it is not joint? Initial it is incompatible, when you write down it in the form of task  and if the system of equations on derivatives thus remains rarefied that SSOR quite to itself an output. If you will apply directly with an initial matrix it simply does not converge.

5

Re: The effective decision big incompatible Slough

Hello, phprus, you wrote: P> There is certainly incompatible Slough (the order of 10000 variables and 40000 equations) for which it is necessary to search for the decision in sense of minimization of a discrepancy. P> system strongly rarefied - in each equation 1 or 2 variable, and remaining coefficients certainly zero... It is possible algorithms and implementations from here to try http://faculty.cse.tamu.edu/davis/suitesparse.html

6

Re: The effective decision big incompatible Slough

Hello, denisko, you wrote: P>>>> Prompt, please, that I can do not so? D>>> it is necessary to Profile. D>>> frequent enough errors - the data  too  or on everyone  the heap when from the abstract layers is caused P>> All time spent inside MKL (even in one function - LAPACKE_dgels or LAPACKE_dgesv depending on a variant). The share of my code in the general time is insignificant. P>> the dense matrixes in API MKL it is simple the unit of the continuous storage. Any abstractions here are impossible even theoretically. P>> on the other hand matlab unambiguously uses rarefied storage for on all task less gigabyte of storage suffices it, and for storage of the dense matrix 10*40 in double it is required more than 3 Gb. D> I.e. you try to transform a disperse matrix to dense and then to solve methods for the dense? Well then it is absolutely bad way. Try from eigen  solvers. The rarefied solver from eigen (Eigen:: SparseQR) tried. On small tasks (the order of 1000 variables) it of time in 2-3 more slowly, than application of methods for the dense matrixes from Intel MKL. On the test of a matrix of the real sizes (variables: 9868, the equations: 39472) eigen it turned out more slowly approximately in 20 times.

7

Re: The effective decision big incompatible Slough

Hello, andyp, you wrote: A> Hello, phprus, you wrote: P>> There is certainly incompatible Slough (the order of 10000 variables and 40000 equations) for which it is necessary to search for the decision in sense of minimization of a discrepancy. P>> system strongly rarefied - in each equation 1 or 2 variable, and remaining coefficients certainly zero... A> It is possible algorithms and implementations from here to try A> http://faculty.cse.tamu.edu/davis/suitesparse.html Thanks for the link, I read about this library, but there, unfortunately, license GPL which does not approach me. Can be there are good analogs under LGPL or, what is more preferable, BSD, Apache, MPL, etc?

8

Re: The effective decision big incompatible Slough

Hello, phprus, you wrote: P> Thanks for the link, I read about this library, but there, unfortunately, license GPL which does not approach me. P> can be there are good analogs under LGPL or, what is more preferable, BSD, Apache, MPL, etc? To tell the truth, I do not know. The author of this  like just in  sparse QR also did. At it the book under the decision of rarefied systems is also articles on a subject. There the mountain of a software using it  is enumerated, and in license.txt is written, what with it it is possible to communicate, that (it is visible???) to bribe the necessary license.

9

Re: The effective decision big incompatible Slough

Hello, phprus, you wrote: P> Thanks for the link, I read about this library, but there, unfortunately, license GPL which does not approach me. What hinders to try? Can on speed does not approach. If arranges to try most to implement the necessary algorithm.

10

Re: The effective decision big incompatible Slough

Hello, andyp, you wrote: A> Hello, phprus, you wrote: P>> Thanks for the link, I read about this library, but there, unfortunately, license GPL which does not approach me. P>> can be there are good analogs under LGPL or, what is more preferable, BSD, Apache, MPL, etc? A> To tell the truth, I do not know. The author of this  like just in  sparse QR also did. At it the book under the decision of rarefied systems is also articles on a subject. There the mountain of a software using it  is enumerated, and in license.txt is written, what with it it is possible to communicate, that (it is visible???) to bribe the necessary license. Yes? Then it will be necessary to test and compare speed of operation. Most likely for this purpose. And I even can assume, how many zero will be in the possible account

11

Re: The effective decision big incompatible Slough

Hello, phprus, you wrote: P> Yes? Then it will be necessary to test and compare speed of operation. P> most likely for this purpose. And I even can assume, how many zero will be in the possible account Depends on application of the Teacher, as a rule, are reasonable enough. If you can convince him that by means of it  you cook a soup for the homeless the account will be hardly too great - something always better than anything. PS the author compares the algorithm (Algorithm 915, there is article in ACM Transactions) with  MA49 http://www.hsl.rl.ac.uk/catalogue/ma49.html it like more slowly, but, may be, that it to buy more cheaply.

12

Re: The effective decision big incompatible Slough

Hello, phprus, you wrote: P> Kind time of days! P> there is certainly incompatible Slough (the order of 10000 variables and 40000 equations) for which it is necessary to search for the decision in sense of minimization of a discrepancy. P> system strongly rarefied - in each equation 1 or 2 variable, and remaining coefficients certainly zero. P> at a model development cycle in matlab for the decision of this task function mldivide which fulfilled less than for 0,1 was used.  like itself can generate C\C ++ the code?