▼
Posts: 901
Threads: 113
Joined: Jun 2007
Rodger: You are correct about the typo. My apologies.
I sort of remember that I encountered other instances (but rarely and not only with RREF solutions) where the product of the solution vector and the input matrix yield exactly the input vector. I will try to find them.
The RREF solutions on my TI83+ and TI95 do some strange things. I'll include a couple of examples with my next submission.
▼
Posts: 1,755
Threads: 112
Joined: Jan 2005
Hi, Palmer:
Glad to see you obviously do appreciate my system (judging from the extreme amounts of time you seem to have dedicated to it since I first posted it here) which is
of course based in no other than my Albillo Matrix AM#7, only its elements have been divided by 10 to make them noninteger and so try and fool 'smart' solvers which will tweak their computations (to force an integer determinant, for instance) if they detect that all matrix elements are integer to begin with.
This division by 10 has no effect on the exact solution, of course, but the determinant becomes 1E7 instead of the original 1. For machines that use some kind of binary representation, you would use either the integer values proper or else divide all elements by two (the determinant would then be 2^7), to still have an *exact* internal representation, unlike Hilbert's matrices.
By the way, I suggest you try the following with this system: just change the order of the rows when inputting the system, and recompute the solution. You'll find that simply changing the order of the rows does bring significantly different results. Same for columns, of course.
Thanks for your interest in my humble production and
Best regards from V.
▼
Posts: 305
Threads: 17
Joined: Jun 2007
Valentin said:
Glad to see you obviously do appreciate my system (judging from the extreme amounts of time you seem to have dedicated to it since I first posted it here) which is of course based in no other than my Albillo Matrix AM#7, only its elements have been divided by 10 to make them noninteger and so try and fool 'smart' solvers which will tweak their computations (to force an integer determinant, for instance) if they detect that all matrix elements are integer to begin with.
Valentin, do you know of any calculators that do that other than the HP48G and similar Saturn based (or emulated Saturn based) calculators?
▼
Posts: 1,755
Threads: 112
Joined: Jan 2005
No. And I think it is a very dangerous thing to do. I'm sure it would be possible to concoct a sample system with integer coefficients where this absurd strategy flunks out badly, resulting in a larger error than if the computed result were left alone.
I hope it is at least flagcontrollable so the user can disable it for good.
Best regards from V.
▼
Posts: 362
Threads: 30
Joined: Jul 2005
Quote:
I hope it is at least flagcontrollable so the user can disable it for good.
It is user controllable. However the flag (flag 54) does not have a very meaningful name:
Tiny element > 0
or
Use tiny element
It is cleared by default (which you think is a bad idea) and the recent manuals (I don't have a 48S) do not help.
The excellent AUR does however explain this flag in some details. But more in line with its name than what it does when all values are integers.
Actually I only recently found out what this flag I was always wondering about, was really doing by following this forum. Thanks once again Valentin.
Arnaud
Edited: 28 Mar 2006, 1:09 p.m.
Posts: 901
Threads: 113
Joined: Jun 2007
In some correspondence not related to simultaneous equation solutions  yes, I really do do other things  my friend Charlie Williamson told me that one of his favorite quotations was by Richard Hamming:
"The purpose of computing is insight, not numbers."
I trust that is what we are doing here.
Posts: 163
Threads: 7
Joined: Jul 2007
Hi, Valentin!
You wrote:
Quote:
<..> which is
of course based in no other than my Albillo Matrix AM#7, only its elements have been divided by 10 to make them noninteger and so try and fool 'smart' solvers which will tweak their computations (to force an integer determinant, for instance) if they detect that all matrix elements are integer to begin with.
The 'tweaker' in the 48G/49 is a little smarter than that, scaling by a power of 10 does not fool it.
With flag 54 clear, DET(A) = 1 and DET(A/10) = 10^7, exactly.
With flag 54 set, DET(A) = .998918882, and DET(A/10) = 9.98918882e08
(A= the original integer Albillo Matrix)
What happens is that when flag 54 is clear, the machine will first determine the exponent of the least significant digit of all entries
So, for A, that would be 0, and for A/10 that is 1
It then calculates the determinant, and then tweaks it as follows:
(exp is the exponent of the lsd, n is the order of the matrix)
t := 10^(exp*n);
DET := ROUND(DET/t)*t;
As you can see, for A the determinant is rounded to the nearest integer, while for A/10 it is premultiplied by 10^7, then rounded to the nearest integer, and then scaled back.
The tweaking will not happen when flag 54 is set, or when all matrix elements are zero, or when the order of the matrix is larger than or equal to 79 (for then the scaling factor might overflow even in extended precision).
Quote:
This division by 10 has no effect on the exact solution, of course, but the determinant becomes 1E7 instead of the original 1. For machines that use some kind of binary representation, you would use either the integer values proper or else divide all elements by two (the determinant would then be 2^7), to still have an *exact* internal representation, unlike Hilbert's matrices.
Division by 2 still results in exact representation, but this time the tweaker is partly fooled:
A A/2 A/4
Exact 1 .0078125 6.103515625E5
54 Clear 1 .0078041 6.087161937E5
54 Set .998918882 7.80405376562E3 6.08716193719E5
We can see where the tweaked values come from by looking at the last row. The value for A/2 is multiplied by 10^7, rounded to the nearest integer, and divide by 10^7. For A/4, the same goes, but with a scaling factor of 10^14.
BTW, the computed determinant (flag 54 set) for A/2 is exactly DET(A)/128, but DET(A/4) is no longer DET(A/2)/128.
Quote:
By the way, I suggest you try the following with this system: just change the order of the rows when inputting the system, and recompute the solution. You'll find that simply changing the order of the rows does bring significantly different results. Same for columns, of course.
? Changing the row order has no effect whatsoever, for LUdecomposition with row interchange is used, on the 48G and 49G
Cheers, Werner
▼
Posts: 1,755
Threads: 112
Joined: Jan 2005
Hi, Werner:
Werner posted:
"? Changing the row order has no effect whatsoever, for LUdecomposition with row interchange is used, on the 48G and 49G"
Yes, I know, but did you actually try it out (with the proper flag setting, of course) ? Because it *does* make a noticeable difference in my HP71B, which also uses LUdecomposition as far as I know.
Best regards from V.
▼
Posts: 163
Threads: 7
Joined: Jul 2007
Hi Valentin, yes I did try it, but not extensively.
I'll try it in detail later, both on a 48G and a 48S (or a 42S, which delivers the exact same results).
Maybe the 71B swaps columns? But then, altering the order of the columns should have no effect.
I'm also a bit suspicious that the 48G delivers the exact solution, while a 48S has several entries completely off the mark. Yet a 48G works with just three more digits (and a 48S uses 15 digits for the dot products, reminiscent of 'floating2'). For system solving, flag 54 is disregarded.
Must be a coincidence (the exact solution, that is). I'll look up your other matrices and see how they fare.
Cheers, Werner
▼
Posts: 1,755
Threads: 112
Joined: Jan 2005
Hi again, Werner:
Werner posted:
"Maybe the 71B swaps columns? But then, altering the order of the columns should have no effect."
Yes, you're right, my original "Mean Matrices" article recently published
in Datafile discussed a particular column (not row) swapping example but all the same it should make no difference. This in an excerpt featuring the specific example:
" 13 72 57 94 90 92 35
40 93 90 99 1 95 66
48 91 71 48 93 32 67
AM #7 = 7 93 29 2 24 24 7
41 84 44 40 82 27 49
3 72 6 33 97 34 4
43 82 66 43 83 29 61
AM #7b = 13 72 57 94 92 90 35
40 93 90 99 95 1 66
48 91 71 48 32 93 67
7 93 29 2 24 24 7
41 84 44 40 27 82 49
3 72 6 33 34 97 4
43 82 66 43 29 83 61
This last one vividly shows that, when dealing with
illconditioned matrices, even merely reordering the rows
and columns can have a great impact on accuracy.
For example, this reordering makes the HP71B’s DET command
return the value:
0.0611338355796
whereas the original ordering (AM #7, above) gave:
0.0699243217409
instead, a 12% difference (in absolute value)"
[and both absolutely off the mark, the true determinant is exactly 1 !!]
I think that having a 12% difference by the mere fact of
swapping columns 5 and 6, for such a small matrix with 12 digit integer coefficients, working with 12digit outputs obtained from 15digit internal arithmetic is certainly quite noticeable, isn't it ?
My article fully discusses further manipulations with this particular matrix, comparing the HP71B results versus exact arithmetic and exact results for diverse 'perturbed' versions of AM#7, you might want to have a look at it.
Best regards from V.
Edited: 30 Mar 2006, 7:37 a.m.
▼
Posts: 163
Threads: 7
Joined: Jul 2007
Hi Valentin.
I was wrong, the 71B uses row exchanges and indeed, row swapping does not alter the determinant or system solution in any way (well as far as I've been able to tell), but of course column swapping does. And the condition of this matrix is so bad (10^12) that the slightest change is magnified twelvefold.
If you swap two columns 'at the end' as you did, the effect is bound to be smaller than when you swap two columns at the beginning, according to the way the algorithm is implemented.
If you swap columns 1 and 2, for instance, the determinant becomes:
0.857871535869
which is completely different. Again, this is not surprising for such a badly conditioned matrix.
The algorithm in the 71B differs slighly from the one in the 42S and 48S, however, since the determinant for the original AM#7 is different. Strangely enough, the determinant for AM7b is the same.
(Moreover  when solving a system, the 71B will alter a singular matrix by a small amount to always return a result, as the 15C does, but it also adds an iterative refinement step  which, in this case, only makes matters worse).
Cheers, Werner
▼
Posts: 1,755
Threads: 112
Joined: Jan 2005
Hi, Werner:
Thanks a lot. Very interesting, your sleuthing :)
Nice matrix this AM #7, uh ? Who could tell, from its perfectly
innocent looks ... ;)
Best regards from V.
Posts: 305
Threads: 17
Joined: Jun 2007
Quote:
Rodger: You are correct about the typo. My apologies.
I sort of remember that I encountered other instances (but rarely and not only with RREF solutions) where the product of the solution vector and the input matrix yield exactly the input vector. I will try to find them.
The RREF solutions on my TI83+ and TI95 do some strange things. I'll include a couple of examples with my next submission.
Apology? No apology needed! It's next to impossible to type in a bunch of numbers like that without a typo or two. I wish I had a way to cut and paste.
By the way, Palmer, would you type VERSION into your HP49 emulator and see what version of the firmware it's emulating?
Here some little programs to play with. Assuming you have a directory on your HP49(G+) with Valentin's original A and B matrices in variables of those names, type in:
SRREF (Expects B and A on the stack; solves via RREF; leaves solution vector on the stack like B/A does)
<< SWAP { 7 } RDM 8 COL+ RREF 8 COL SWAP DROP { 7 1 ) RDM >>
IREF (Does iterative refinement; needs stack to have B A X on levels 3, 2 and 1; keeps B and A on stack above the solution vector so the IREF function can be executecd repeatedly; X is the solution vector which was obtained by any method, such as B/A or SRREF)
<< 3 DUPN RSD 3 PICK / + >>
TST0 (calculates the residual of a solution; expects B A X on the stack; the calculated residual can be dropped and B A X will still be on the stack for further testing; deliberately DOESN'T use the RSD function; if the test solution is exact, the residual will be all zeroes)
<< DUP 3 PICK SWAP * 4 PICK  >>
So, having all this in your directory, type B A B A then press SRREF. The solution vector will be on level 1. Now press TST0 and see [0 0 0 0 0 0 0], indicating the solution was exact (with 12digit floating point arithmetic, that is). Now DROP the residual off the bottom of the stack and press IREF to get a new solution vector; press TST0 again and see that this solution is also exact (the residual is [0 0 0 0 0 0 0]); DROP the residual after you examine it. If you press IREF a few more times, you'll eventually get the solution [1 1 1 1 1 1 1].
Start over with B A B A on the stack and then press SSREF. Press TST0 and note that the solution is exact; DROP the residual. Now enter a number close to 1; say between .9 and 1.1 such as .98456; press * to multiply every element of the solution vector by that number. Press TST0 to see that the solution is NOT exact; DROP that result off the stack and press IREF to do iterative refinement once. Now TST0 and see that the new solution vector is exact (in 12digit arithmetic, of course); DROP the residual. Occasionally this doesn't work and the solution vector isn't quite exact; if this happens, IREF again and it will almost always be exact this time. Always remember to DROP the residual from TST0 before you do any more IREFs. Multiply the solution vector again by some number between .9 and 1.1 and then IREF. You will almost always get an exact solution vector, different from any previous one. This is one way to show that there are a LOT of solution vectors that are "exact" in 12digit floating point arithmetic.
