# Solving $AXB + X\odot C = D$ matrix equation

Can anyone see a way to solve this equation efficiently?

$$AXB + X\odot C = D$$

I tried a straightforward solution that involved vectorizing $$X$$ but that turned out too expensive for my application -- my matrices are all $$d\times d$$ with $$d=1000$$ so I'm seeing if there's a way to solve it at a cost comparable to $$d\times d$$ SVD.

$$A$$,$$B$$ are positive-semi-definite and $$C$$ may have a few zeros.

• Have you tried solving the vectorized equation with an iterative method, such as GMRES? You can use the non-vectorized form to compute the matrix-vector product in \$O(d^3), so your total cost would be comparable to SVD if the number of iterations is small. You might need a preconditioner though. – Amit Hochman Sep 28 '19 at 14:25
• @YaroslavBulatov I added "matrix-equations", correct me if I am wrong. – Anton Menshov Sep 29 '19 at 19:37
• – Federico Poloni Sep 30 '19 at 11:24
• Where it appears to have an answer. Please post on one site at a time only. – Richard Sep 30 '19 at 23:46
• I'm starting to think that this problem is not solvable in O(d^3). It comes from approximating T=E[xi,xj,xk,xl] in terms of lower order moments, then trying to solve TX=G. I found that even computing ||T||^2 needs more than O(d^3) operations – Yaroslav Bulatov Oct 2 '19 at 17:52