Message Boards Message Boards

2
|
7687 Views
|
7 Replies
|
9 Total Likes
View groups...
Share
Share this post:

Accuracy of matrix computations in Wolfram compared to Python's numpy?

UPD1: I loaded original data set in .txt format. There are two columns in the file: first for x values and second for phi[x] values.

Preface

The question arised during the work on a computational mathematics home task in my university. Please note that here in the preface I explain only the background of my question. For the question itself see the following chapters. The task was simple: based on a set ob "observed" values of an unknown function phi[x] construct a polynomial approximation of this function:

f[x_] := Sum[c[[i + 1]] * P[i, x], {i, 0, M}]

Here c is a list of expansion coefficients, P[i, x] is a polynomial of i-th degree of x (from any orthogonal system, e.g. Legendre's polynomial) and M is some pre-defined (set by the instructor) number. We had to find coefficients from the list c.

If the unknown function phi[x] was measured in N points from a list x = {x1, x2, ..., xN} then this problem can be re-written in form of reduntant system of linear equations with N rows and M columns:

c[[1]] * P[0, x1] + c[[2]] * P[1, x1] + ... + c[[M + 1]] * P[M, x1] == phi[x1];
c[[1]] * P[0, x2] + c[[2]] * P[1, x2] + ... + c[[M + 1]] * P[M, x2] == phi[x2];
...
c[[1]] * P[0, xN] + c[[2]] * P[1, xN] + ... + c[[M + 1]] * P[M, xN] == phi[xN];

Or in matrix form:

Dot[A, c] == phi[x]

We had to solve this system with two methods: using QR-decomposition of the matrix A and simply multiplying both sides by Transpose[A] and then solving a new system with a square positive-defined matrix using, for example, Cholesky method:

Dot[Transpose[A], A].c == Dot[Transpose[A], phi[x]]

The problem

All the calculations were not difficult and the resulting approximation was quite good. As a part of the task report we had to compute condition number of both matrices A and Transpose[A].A in spectral norm:

condA = First[#] / Last[#]&@SingularValueList[A];
condATA = First[#] / Last[#]&@SingularValueList[Traspose[A].A]

And here quite surprising things happened. According to "obvious" (and naive actually) estimate condATA should grow with increase of the maximal polynomial degree as square of condA:

condATA ~ condA^2 (*as max degree M grows*)

And this rule was satisfied for small (1 - 7) values of M. But then condATA stopped growing and finally for M ~ 10-20 both condition numbers started oscillating around level of 10^9 - 10^13.

Since we were not restricted in the programming language that we use in this task, a lot of my groupmates chose Python as their working tool. And in Python the rule mentioned above worked even for big M: condATA grew as square of condA reaching values of 10^18 and higher. MATLAB computations gave similar results.

The question

So, the question is: which results are correct - those obtained in Mathematica or those computed in Python's numpy library and MATLAB? I worked in machine precision, accuracy of the condition number condATA varied from ~11 for small degrees to ~2.6 for M = 10 (I mean results of the Accuracy[] function). No warnings arised during its computation.

And if Mathematica is wrong how can I avoid such situations in future?

Some words in the end

This is my first post here in the Wolfram Community, so if you have suggestions on the style please write them in the comments. I also apologize for all possible mistakes in my English.

Attachments:
POSTED BY: Nikolay Shilov
7 Replies

Thank you Daniel and J.M.

Both pieces of advice were helpful. In my original solution for a certain M I had condA ~ 10^13 and condATA ~ 10^13. Artificial increase of precision (from MachinePrecision to 20) led to grows of condition number condATA by a factor of 10^3. Setting Tolerance option in SingularValueList equal to 0 made condATA increased condATA to 10^17. Value of condA remained (almost) unchanged.

By the way, applying both recommendations - increasing precision to 20 and setting Tolerance to 0 - results in brilliant correspondance of condATA and condA^2 (their ratio would be equal to 0.99999999999991). It looks the problem is solved.

POSTED BY: Nikolay Shilov

It is also worth to note that actual precision of the available data seems to be 8. And setting it directly using SetPrecision[] yelds good results with predictable growth of condATA (as sqare of condA) only for limited range of powers M. If everything written on arbitrary-precision calculations in the Wolfram Language Documentation is true than I can conclude that this is ultimate limitation and all calculations with higher values of M are incorrect.

POSTED BY: Nikolay Shilov

It is not clear to me what is the statement or if there is a question here. Certainly if precision is 8, artificially raising it using SetPrecision will not give "better" results other than perhaps to work around any limitations that the original low precision might impose (and I am not sure there are any in this case).

I can say a bit about the arbitrary precision documentation and numeric linear algebra in the Wolfram Language. Much of the latter is implemented using fixed precision arithmetic, with condition number estimates or other means used to lower precision/accuracy in the results. The error propagation model of significance arithmetic is simply too large for effective use in the context of numeric linear algebra.

Getting back to the original scenario, as best I understand it. There is a dimension parameter, m, and a parametrized family of matrices mat[m]. Precision of the entries is on the order of 8 digits in all cases. The matrices become more ill-conditioned as m goes up. If that is a correct understanding, then the remark about eventual incorrectness is on target. In effect each matrix is actually a Cartesian product of intervals (each element represents an interval of a value +-10^(-8), that is). Any linear algebra computation will give an approximation to a result that applies at best to some members of the original interval product. If the conditioning is bad then this approximation might be quite bad, and indeed error might swamp approximation.

POSTED BY: Daniel Lichtblau
Posted 5 years ago

I can say a bit about the arbitrary precision documentation and numeric linear algebra in the Wolfram Language. Much of the latter is implemented using fixed precision arithmetic, with condition number estimates or other means used to lower precision/accuracy in the results. The error propagation model of significance arithmetic is simply too large for effective use in the context of numeric linear algebra.

In the other words, linear algebra functions do support operations with numbers having arbitrary precision, but without error tracking for each individual arithmetic operation: the error propagation is simulated with other means?

POSTED BY: Alexey Popkov

Yes, as best I recall any error estimation is done differently e.g. using a condition number estimate.

I should add that it has been a very long time since I looked at the bignum linear algebra code.

POSTED BY: Daniel Lichtblau

As J.M. notes, it is difficult to say much without the concrete examples. But I can venture a guess based on what is shown. SingularValueList is using the default Automatic setting for the Tolerance option. In this setting it will discard singular values that are beneath a threshold which is, I believe, a couple of orders of magnitude larger than largest singular value times 10^(-$MachinePrecision). So you are very likely not actually using the smallest singular value in that condition number estimate.

POSTED BY: Daniel Lichtblau
Posted 5 years ago

Without the data you used to compute your matrix coefficients, it is hard to say anything substantial. Presumably you know the rule of thumb that you can lose up to $\approx \log_b(\kappa)$ base-$b$ digits in your solution?

In the meantime, here is a sketch of an experiment for you to try: use SetPrecision[] to (artificially!) increase the precision of your starting numerical data, and attempt the condition number calculations again; the results should ideally not be too different, and if they are markedly different, then you certainly have something worth investigating deeply.

Finally, you're computing and then throwing away the medium-sized singular values for computing $\kappa_2$; try using Norm[mat]/First[SingularValueList[mat, -1, Tolerance -> 0]] instead.

POSTED BY: J. M.
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract