We’re rewarding the question askers & reputations are being recalculated! Read more.

 2 added 170 characters in body edited Oct 24 '16 at 8:51 Federico Poloni 4,5171414 silver badges2727 bronze badges Have you considered working with the Cholesky (or low-rank) factor of $$\rho(t_0)$$ rather than with the matrix itself? This might reduce the number of products that you need to make, and it has the additional benefit of preserving positive semidefiniteness across your computations. It is already cheaper to use Cholesky factors for this computation alone, if I am not making mistakes with the costs: let $$n$$ be the side of each matrix appearing here; computing the upper triangular Cholesky factor $$R$$ such that $$\rho(t_0)=R^\dagger R$$ costs $$\frac13 n^3$$ (counting with the traditional model addition=multiplication=1); computing $$RU$$ costs $$n^3$$ (because $$R$$ is triangular), and computing $$(RU)^\dagger (RU)$$ costs $$n^3$$ (because you only need to compute half of the entries). OTOH, computing $$U^\dagger \rho(t_0)$$ costs $$2n^3$$, and then computing half of the entries of $$(U^\dagger \rho(t_0))U$$ costs $$n^3$$. If $$\rho(t_0)$$ has low rank (which, at least in the examples I saw when I studied quantum mechanics, happened quite often for initial states), then one can start from a rectangular $$R$$ coming from the QR of its low-rank factor rather than a Cholesky decomposition, and this method is even cheaper. If you have to make more computations with your matrices after this triple product, then there may be additional savings in further steps: for instance, to compute products and solve linear system you can work with the low-rank factors directly rather than forming the last product. Have you considered working with the Cholesky (or low-rank) factor of $$\rho(t_0)$$ rather than with the matrix itself? This might reduce the number of products that you need to make, and it has the additional benefit of preserving positive semidefiniteness across your computations. It is already cheaper to use Cholesky factors for this computation alone, if I am not making mistakes with the costs: let $$n$$ be the side of each matrix appearing here; computing the upper triangular Cholesky factor $$R$$ such that $$\rho(t_0)=R^\dagger R$$ costs $$\frac13 n^3$$ (counting with the traditional model addition=multiplication=1); computing $$RU$$ costs $$n^3$$ (because $$R$$ is triangular), and computing $$(RU)^\dagger (RU)$$ costs $$n^3$$ (because you only need to compute half of the entries). OTOH, computing $$U^\dagger \rho(t_0)$$ costs $$2n^3$$, and then computing half of the entries of $$(U^\dagger \rho(t_0))U$$ costs $$n^3$$. If $$\rho(t_0)$$ has low rank (which, at least when I studied quantum mechanics, happened quite often for initial states), then one can start from a QR of its low-rank factor rather than a Cholesky decomposition, and this method is even cheaper. If you have to make more computations with your matrices after this triple product, then there may be additional savings in further steps. Have you considered working with the Cholesky (or low-rank) factor of $$\rho(t_0)$$ rather than with the matrix itself? This might reduce the number of products that you need to make, and it has the additional benefit of preserving positive semidefiniteness across your computations. It is already cheaper to use Cholesky factors for this computation alone, if I am not making mistakes with the costs: let $$n$$ be the side of each matrix appearing here; computing the upper triangular Cholesky factor $$R$$ such that $$\rho(t_0)=R^\dagger R$$ costs $$\frac13 n^3$$ (counting with the traditional model addition=multiplication=1); computing $$RU$$ costs $$n^3$$ (because $$R$$ is triangular), and computing $$(RU)^\dagger (RU)$$ costs $$n^3$$ (because you only need to compute half of the entries). OTOH, computing $$U^\dagger \rho(t_0)$$ costs $$2n^3$$, and then computing half of the entries of $$(U^\dagger \rho(t_0))U$$ costs $$n^3$$. If $$\rho(t_0)$$ has low rank (which in the examples I saw when I studied quantum mechanics happened quite often for initial states), then one can start from a rectangular $$R$$ coming from the QR of its low-rank factor rather than a Cholesky decomposition, and this method is even cheaper. If you have to make more computations with your matrices after this triple product, then there may be additional savings: for instance, to compute products and solve linear system you can work with the low-rank factors directly rather than forming the last product. 1 answered Oct 24 '16 at 6:57 Federico Poloni 4,5171414 silver badges2727 bronze badges Have you considered working with the Cholesky (or low-rank) factor of $$\rho(t_0)$$ rather than with the matrix itself? This might reduce the number of products that you need to make, and it has the additional benefit of preserving positive semidefiniteness across your computations. It is already cheaper to use Cholesky factors for this computation alone, if I am not making mistakes with the costs: let $$n$$ be the side of each matrix appearing here; computing the upper triangular Cholesky factor $$R$$ such that $$\rho(t_0)=R^\dagger R$$ costs $$\frac13 n^3$$ (counting with the traditional model addition=multiplication=1); computing $$RU$$ costs $$n^3$$ (because $$R$$ is triangular), and computing $$(RU)^\dagger (RU)$$ costs $$n^3$$ (because you only need to compute half of the entries). OTOH, computing $$U^\dagger \rho(t_0)$$ costs $$2n^3$$, and then computing half of the entries of $$(U^\dagger \rho(t_0))U$$ costs $$n^3$$. If $$\rho(t_0)$$ has low rank (which, at least when I studied quantum mechanics, happened quite often for initial states), then one can start from a QR of its low-rank factor rather than a Cholesky decomposition, and this method is even cheaper. If you have to make more computations with your matrices after this triple product, then there may be additional savings in further steps.