I have two problems related to computing some trace, and some (possibly suboptimal) answers. My question is about a potential more efficient algorithm for each one. (More interested in an answer to question 1.)

1. Let $U, V$ and $F$ be three real matrices. All three matrices have size $d \times r$, with $r \ll d$ (that is, $U, V$ and $F$ are ``tall''). I want to compute $\mathrm{trace}(U V^\top F F^\top)$. Computing $A = F^\top U$, $B = V^\top F$ and the trace of $AB$ has complexity $\mathcal{O}(r^2 d)$. Is there any faster algorithm (taking into account $r \ll d$)? Can we get $\mathcal{O}(r d)$?

2. Let $U, V$ and $M$ be three real matrices. $U$ and $V$ have size $d \times r$ (with $r \ll d$), and $M$ is lower triangular (with positive elements in its diagonal) of size $d \times d$. I want to compute $\mathrm{trace}(U V^\top M M^\top)$. The simple algorithm of computing $A = M^\top U$, $B = V^\top M$, and then the trace of $AB$ has a complexity $\mathcal{O}(r d^2)$. Is there any faster algorithm (taking into account $r \ll d$)?

If this question does not belong here please let me know! (If so, also where can I post it.)

Thanks!