# 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. Sep 28, 2019 at 14:25
• @YaroslavBulatov I added "matrix-equations", correct me if I am wrong. Sep 29, 2019 at 19:37
• Sep 30, 2019 at 11:24
• Where it appears to have an answer. Please post on one site at a time only. Sep 30, 2019 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 Oct 2, 2019 at 17:52