1

Topic: The decision of the matrix equation

All greetings! There was a necessity of the decision of the matrix equation following not quite normal type: \sum _ {i} A_i*X*A_i^T = \sum _ {i} B_i Matrixes A_i, B_i - known, X - required, all square NxN. It is clear that 1) it is possible to count total B_i in advance, but, probably, this root form in the form of the total is capable to help something... 2) the matrix X can be drawn out in a vector and then one long linear system with a size N^2 turns out. But it to solve, accordingly, much longer, and to make . Any rather simple approaches operating only with matrixes NxN are Perhaps, known? Stick into the literature...

2

Re: The decision of the matrix equation

Hello, kfmn, you wrote: K> There was a necessity of the decision of the matrix equation following not quite normal type: K> \sum _ {i} A_i*X*A_i^T = \sum _ {i} B_i K> Matrixes A_i, B_i - known, X - required, all square NxN. It is clear that K> 1) it is possible to count total B_i in advance, but, probably, this root form in the form of the total is capable to help something... K> 2) the matrix X can be drawn out in a vector and then one long linear system with a size N^2 turns out. But it to solve, accordingly, much longer, and to make . And in what  here also is N*N the equations

3

Re: The decision of the matrix equation

Hello, kfmn, you wrote: K> All greetings! K> there was a necessity of the decision of the matrix equation following not quite normal type: K> \sum _ {i} A_i*X*A_i^T = \sum _ {i} B_i K> Matrixes A_i, B_i - known, X - required, all square NxN. It is clear that K> 1) it is possible to count total B_i in advance, but, probably, this root form in the form of the total is capable to help something... K> 2) the matrix X can be drawn out in a vector and then one long linear system with a size N^2 turns out. But it to solve, accordingly, much longer, and to make . Here only a way 2 . In X N^2 elements. Hardly something will be easier, than linear equation system for all of them, koeff of which will be the totals on i pairwise products el A_i.

4

Re: The decision of the matrix equation

Hello, kfmn, you wrote: K> All greetings! K> there was a necessity of the decision of the matrix equation following not quite normal type: K> \sum _ {i} A_i*X*A_i^T = \sum _ {i} B_i K> Matrixes A_i, B_i - known, X - required, all square NxN. It is clear that K> 1) it is possible to count total B_i in advance, but, probably, this root form in the form of the total is capable to help something... K> 2) the matrix X can be drawn out in a vector and then one long linear system with a size N^2 turns out. But it to solve, accordingly, much longer, and to make . K> any rather simple approaches operating only with matrixes NxN are Perhaps, known? Stick into the literature... You at n=2 will have a type equation: A_1*X*A_1^T + A_2*X*A_2^T = B_1 + B_2 where A_1, A_2, B_1, B_2, X - matrixes NxN you it wanted to tell?

5

Re: The decision of the matrix equation

Hello, kov_serg, you wrote: _> Hello, kfmn, you wrote: K>> There was a necessity of the decision of the matrix equation following not quite normal type: K>> \sum _ {i} A_i*X*A_i^T = \sum _ {i} B_i K>> Matrixes A_i, B_i - known, X - required, all square NxN. It is clear that K>> 1) it is possible to count total B_i in advance, but, probably, this root form in the form of the total is capable to help something... K>> 2) the matrix X can be drawn out in a vector and then one long linear system with a size N^2 turns out. But it to solve, accordingly, much longer, and to make . _> And in what  here also is N*N the equations Well, I simply thought that the standard method of the Gauss for the decision of the equation with matrix NxN demands order N^3 of operations. Accordingly, in my case it pours out already in N^6. And suddenly there are methods, say, to reduce it to a dial-up from N (or even N^2) the equations with matrixes NxN concerning certain vectors which are somehow connected to a required matrix X and to recover it on them... Or still something that from 6th level to pass somewhere more low...

6

Re: The decision of the matrix equation

Hello, Alex.a777, you wrote: AA> you at n=2 will have a type equation: AA> A_1*X*A_1^T + A_2*X*A_2^T = B_1 + B_2, AA> where A_1, A_2, B_1, B_2, X - matrixes NxN AA> you it wanted to tell? Yes, all matrixes - dimensionalities NxN, and items in the total - a certain fixed amount which with N is not connected in any way, can be and 2.

7

Re: The decision of the matrix equation

Hello, kfmn, you wrote: K> Hello, Alex.a777, you wrote: AA>> you at n=2 will have a type equation: AA>> A_1*X*A_1^T + A_2*X*A_2^T = B_1 + B_2, AA>> where A_1, A_2, B_1, B_2, X - matrixes NxN AA>> you it wanted to tell? K> yes, all matrixes - dimensionalities NxN, and items in the total - a certain fixed amount which with N is not connected in any way, can be and 2. 1) Well the method of the Gauss solves the equation of type AX=B. How plan it to apply to your system? I so understand, the iterative approach over a method of the decision of Slough? 2) concerning a choice of methods, look https://www.mathworks.com/help/matlab/r … e_full.png

8

Re: The decision of the matrix equation

Hello, Alex.a777, you wrote: AA> Hello, kfmn, you wrote: K>> Hello, Alex.a777, you wrote: AA>>> you at n=2 will have a type equation: AA>>> A_1*X*A_1^T + A_2*X*A_2^T = B_1 + B_2, AA>>> where A_1, A_2, B_1, B_2, X - matrixes NxN AA>>> you it wanted to tell? K>> yes, all matrixes - dimensionalities NxN, and items in the total - a certain fixed amount which with N is not connected in any way, can be and 2. AA> 1) Well the method of the Gauss solves the equation of type AX=B. How plan it to apply to your system? I so understand, the iterative approach over a method of the decision of Slough? AA> 2) concerning a choice of methods, look https://www.mathworks.com/help/matlab/r … e_full.png Probably, I insufficiently clearly expressed about the decision by means of extraction in a vector. I meant the following: if to paint system component-wise (in the scalar form) each of the equations will be linear concerning elements of a matrix X. I.e. If all columns of a matrix X to make in one long vector Y dimensionality N^2 we receive normal Slough of type CY=D, but with matrix N^2xN^2. And to solve it it is possible, but it would be desirable something faster.

9

Re: The decision of the matrix equation

Hello, kfmn, you wrote: K> Hello, Alex.a777, you wrote: AA>> Hello, kfmn, you wrote: K>>> Hello, Alex.a777, you wrote: AA>>>> you at n=2 will have a type equation: AA>>>> A_1*X*A_1^T + A_2*X*A_2^T = B_1 + B_2, AA>>>> where A_1, A_2, B_1, B_2, X - matrixes NxN AA>>>> you it wanted to tell? K>>> yes, all matrixes - dimensionalities NxN, and items in the total - a certain fixed amount which with N is not connected in any way, can be and 2. AA>> 1) Well the method of the Gauss solves the equation of type AX=B. How plan it to apply to your system? I so understand, the iterative approach over a method of the decision of Slough? AA>> 2) concerning a choice of methods, look https://www.mathworks.com/help/matlab/r … e_full.png K> Probably, I insufficiently clearly expressed about the decision by means of extraction in a vector. I meant the following: if to paint system component-wise (in the scalar form) each of the equations will be linear concerning elements of a matrix X. I.e. If all columns of a matrix X to make in one long vector Y dimensionality N^2 we receive normal Slough of type CY=D, but with matrix N^2xN^2. And to solve it it is possible, but it would be desirable something faster. Here you to yourselves invented operation! Did not understand an initiating message, yes)) I do not claim for an optimality, but there is an iterative approach: 0) it is sampled X0 1) we solve Slough rather X_i+1: A_1*X_i+1 = [summ (B_i, i=1, n) - summ (A_i*X_i*A_i^T, i=2, n)] * (A_1^T) ^-1 2) while || X_i+1 - X_i ||> eps X_i = X_i+1 and on a step 1)

10

Re: The decision of the matrix equation

Hello, kfmn, you wrote: K> any rather simple approaches operating only with matrixes NxN are Perhaps, known? Stick into the literature... I would suggest the approach on the other hand - to try to use GPU for operations over matrixes. The machine iron, let considers.

11

Re: The decision of the matrix equation

Hello, Alex.a777, you wrote: AA> Hello, kfmn, you wrote: K>> Hello, Alex.a777, you wrote: AA>>> Hello, kfmn, you wrote: K>>>> Hello, Alex.a777, you wrote: AA>>>>> you at n=2 will have a type equation: AA>>>>> A_1*X*A_1^T + A_2*X*A_2^T = B_1 + B_2, AA>>>>> where A_1, A_2, B_1, B_2, X - matrixes NxN AA>>>>> you it wanted to tell? K>>>> yes, all matrixes - dimensionalities NxN, and items in the total - a certain fixed amount which with N is not connected in any way, can be and 2. AA>>> 1) Well the method of the Gauss solves the equation of type AX=B. How plan it to apply to your system? I so understand, the iterative approach over a method of the decision of Slough? AA>>> 2) concerning a choice of methods, look https://www.mathworks.com/help/matlab/r … e_full.png K>> Probably, I insufficiently clearly expressed about the decision by means of extraction in a vector. I meant the following: If to paint system component-wise (in the scalar form) each of the equations will be linear concerning elements of a matrix X. I.e. if all columns of a matrix X to make in one long vector Y dimensionality N^2 we receive normal Slough of type CY=D, but with matrix N^2xN^2. And to solve it it is possible, but it would be desirable something faster. AA> here you to yourselves invented operation! Did not understand an initiating message, yes)) AA> I do not claim for an optimality, but there is an iterative approach: AA> 0) it is sampled X0 AA> 1) we solve Slough rather X_i+1: A_1*X_i+1 = [summ (B_i, i=1, n) - summ (A_i*X_i*A_i^T, i=2, n)] * (A_1^T) ^-1 AA> 2) while || X_i+1 - X_i ||> eps X_i = X_i+1 and on a step 1) Thanks for idea, but, at first, matrixes A_i can be not reversible, and secondly, whether such process will converge it the big question...

12

Re: The decision of the matrix equation

Hello, Glory, you wrote: Hello, kfmn, you wrote: K>> any rather simple approaches operating only with matrixes NxN are Perhaps, known? Stick into the literature... I would suggest the approach on the other hand - to try to use GPU for operations over matrixes. The machine iron, let considers. A brute force, aha. But if with matrixes 20x20 it  to solve system 400x400 it is not too unprofitable, here with 1000x1000 (initial) - already is not present. Any modern GPU 10^6x10^6 does not gobble up a matrix. At me, of course, matrixes not such huge, are faster, closer to 1 example, but is interesting algorithmic acceleration.

13

Re: The decision of the matrix equation

14

Re: The decision of the matrix equation

Hello, kfmn, you wrote: AA>> Here you to yourselves invented operation! Did not understand an initiating message, yes)) AA>> I do not claim for an optimality, but there is an iterative approach: AA>> 0) it is sampled X0 AA>> 1) we solve Slough rather X_i+1: A_1*X_i+1 = [summ (B_i, i=1, n) - summ (A_i*X_i*A_i^T, i=2, n)] * (A_1^T) ^-1 AA>> 2) while || X_i+1 - X_i ||> eps X_i = X_i+1 and on a step 1) K> Thanks for idea, but, at first, matrixes A_i can be not reversible, and secondly, whether such process will converge it the big question... 1) has enough reversibility of any of matrixes A_i^T. As reference it is possible to select any. If to change a reference matrix not the fact that convergence to be refined, and it is more than restrictions, yes 2) Convergence, I suspect, will be defined by a condition of type of criterion of Skarborou, i.e. In practical sense useless 3) Anyway, most most  for the dense well caused matrixes is either multigrid, or family of iterative methods of Krylov

15

Re: The decision of the matrix equation

Hello, kfmn, you wrote: K> Hello, kov_serg, you wrote: _>> Hello, kfmn, you wrote: K>>> There was a necessity of the decision of the matrix equation following not quite normal type: K>>> \sum _ {i} A_i*X*A_i^T = \sum _ {i} B_i K>>> Matrixes A_i, B_i - known, X - required, all square NxN. It is clear that K>>> 1) it is possible to count total B_i in advance, but, probably, this root form in the form of the total is capable to help something... K>>> 2) the matrix X can be drawn out in a vector and then one long linear system with a size N^2 turns out. But it to solve, accordingly, much longer, and to make . _>> And in what  here also is N*N equations K> Well, I simply thought that the standard method of the Gauss for the decision of the equation with matrix NxN demands order N^3 of operations. Accordingly, in my case it pours out already in N^6. Do not use a gauss method. In the majority a case conjugate gradients (for example https://pdfs.semanticscholar.org/466d/a … df687.pdf) converge much faster. K> and suddenly there are methods, say, to reduce it to a dial-up from N (or even N^2) the equations with matrixes NxN concerning certain vectors which are somehow connected to a required matrix X and to recover it on them... Or still something that from 6th level to pass somewhere more low... If norm of one matrix strongly more others it is possible to use a method of perturbations.

16

Re: The decision of the matrix equation

Hello, kfmn, you wrote: K> the Brute force, aha. But if with matrixes 20x20 it  to solve system 400x400 it is not too unprofitable, here with 1000x1000 (initial) - already is not present. Any modern GPU 10^6x10^6 does not gobble up a matrix. Whether and CPU gobbles up that? 1*1*8 it is 8 Tb of the data, in double precision. 1000*1000 it only 4 mbytes float or 8mb doubles. Modern GPU have from 8 GB onboard. You there the matrixes 1000*1000 can  on-most tomatoes of 1000 matrixes with doubles, dimensionality 1000*1000 everyone. Whether Mahlo that? In the limiting size something sees the order 22000 * 22000 Single Precision for 8GB cards. 4 matrixes gets. Only consider doubles essentially  in modern not-prof cards. For example I 1080ti produces: - 12869 GFlops in Single Precision - 417 GFlops (only) in Double Precision. Ancient Radeon HD7990 did not cut off in double precision, and at it enviable 1821 GFlops, though in unary not impressive 7296 GFlops. Truth of storage at it all on 3GB on the chip. For comparing: 4 nuclear 8 continuous i7-7700K on 4.5 has: - 460 GFlops unary. - 230 GFlops double precision GPU almost in 30 times faster in Single Precision calculations. Besides such volumes will play for certain a role speed of storage. At GPU storage faster time in 10.