Need QR decomposition algoritm.

Question

Hi Miles.

Have you ever considered adding QR decomposition? It is widely used in tensor network simulations.

Thank you.

Answer 1

Yes, I agree we should have this in principle. But overall we've been taking the approach of not adding extra features until someone reports that they have a specific use-case for this. That way we only have features that get used often so that we can stay on top of bugs.

One question is: have you found that the SVD step is an efficiency bottleneck for the algorithm you are performing? In many algorithms the flexibility of the SVD (such as the option to truncate) outweighs the extra cost compared to QR, especially when other parts of the algorithm dominate the run time.

If you do find that QR would speed up your overall code (not just a sub-leading part) I can prioritize adding support for it.

Miles

Comments

Thank you Miles.
I'm working on iPEPS algorithm those days.  Using SVD instead of QR works well for me without lossing of efficiency.
But I don't know whether it will cause any non-instability in the future.
Any way, I managed to add QR decomposition myself with the help of doTask(GetBlocks ...)  function and Eigen library. But doTask(GetBlocks ...) is an inner function and I can not fully understand it.  Thus my code works but looks ugly.
Any way, it well be  a delight if you add QR decomposition to the ITensor library itself. I'v encountered many QR decompositions in tensor network algorithms to factorize square matrices without truncation .
By the way, using denmatDecomp instead of QR does cause a bad_alloc error, but I don't known why.

Best wishes.

---

Based on your use case, it sounds like SVD would actually be a better choice for you. For one thing it's not a bottleneck as you mentioned. I don't see why it would cause an instability, any more than the QR would. Is there a reason you could say more about?

It would be nice for QR to be available in the future, but I may not prioritize it right now as I have very limited time and it sounds like it's not blocking you from doing what you need.

Finally, I don't know either why you got the bad_alloc error. Perhaps you were running out of memory on your system? I could try to reproduce the error to find it if you could provide sample code.

Miles

---

Thank you Miles.
Yesterday I comment "Using SVD instead of QR without lossing of efficiency". That was because I used a debug version of QR but link to a release version of SVD.
In the implement of corner transform matrix reported in PhysRevLett.113.046402, QR does improve the efficiency significantly.  In this implement,  QR is used to factorize Large square matrices without truncation. In fact , only R matrix is required.
So I still suggest adding QR to Itensor. But it is OK if you do not have time, I can manage it myself.
Thank you again for your excellent work.

---

Ok that's helpful to know that it can give a significant speedup in some algorithms. I will put it on my list of features to add, but it will take me probably a month or so to get to it. Sorry I can't do it sooner!

Answer 2

One way is to use SVD decomposition, instead. Do the following,

A=UsV, R := s*V, Q=U

then A=Q*R,

However, R is not an upper triangular matrix, as it should be in the case of QR.

But, I agree adding QR itself to Itensor is more recomended.

Comments

Thank you. It works well.