solve_upper: Tolerance issues for large N?

[philw16]

In the case of solve_upper_triangular, for N of greater than about 70 in the upper triangular matrix my tests will pass only about 50% of the time, with the other times the error being far greater than the tolerance. Is it possible that for a random number upper triangular matrix of this size error can compound to cause this? Or is it a problem in my function itself.

[mvelegar]

I don't see any reason why random number upper (or lower) triangular matrix will give you errors only for N>=70. Please update your repository so that we could look at your function implementation to suggest why this may be happening. Also, are you making sure there are no 0 values on the main diagonal?

[cswiercz]

If you're doing randomized testing (that is, testing the validity of your algorithm using a random upper triangular matrix) then a bug may not be manifested all the time. After all, the input is random and sometimes the random input may work and sometimes it won't depending on the type of bug.

Try with a non-random input where you can calculate the answer by hand. Are there certain kinds of input where your code works and where it doesn't? That can give you a hint on the location of the bug. Use Meghana's hint for some examples:

Also, are you making sure there are no 0 values on the main diagonal?

[philw16]

So I have added the condition that makes sure there are no zeros in the main diagonal to my function. I guess what is throwing me off is that there are no problems with lower values of N. Is it possible that if the random values are generated to a large value (lets say on the order of 10^32 because that's what popped up in my most recent run), that the computation of the norm between the values could accumulate some error? Because upon inspection they appear to be the same. And even in a comparison between the two vectors asserting each component was almost equal, this is the error I receive:

AssertionError: -8.5111537694437344e+28 != -8.5111537694437326e+28 within 7 places

Even though this is accurate to 11 decimals in

[philw16]

So feeding off this question, is there a bound to the size of the numbers (not the matrices themselves) that our code will be tested against?

[quantheory]

I should point out that large, random triangular matrices are ill-conditioned. I've talked about this a little bit with another student on the gitter chat, if you want to look that up. If you are solving Ax=b for x, you can "check the answer" by calculating the norm of Ax-b using the calculated x. If you are not getting a very small number even with the built-in numpy solver, that's a hint that your matrix is ill-conditioned and you should not expect to be able to get a good answer at all (using conventional floating-point arithmetic).

[quantheory]

And yes, I presume that in the tests, we will use matrices that are well-conditioned enough that your code can reasonably be expected to get a good answer. (This is not the same thing as a "bound to the size of the numbers" exactly, but it's a similar idea.)

[philw16]

That made things a lot more clear. Thank you!

[alyfarahat]

A small addition to @quantheory , I usually force the diagonal elements of U or L to likely generate a "well-conditioned" matrix. One way to do that is to force the diagonal to be equal to the size of one dimension of the matrix. For example, if I choose normally random distributed elements from from -1 to 1 in a matrix of dimension 1000 x 1000, choose the diagonal values to be 1000. This worked for me for matrices as large as 10000 x 10000