Re: Even More Simultaneous Equation Solutions



#4

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 TI-83+ and TI-95 do some strange things. I'll include a couple of examples with my next submission.


#5

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 non-integer 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 1E-7 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.


#6

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 non-integer 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?


#7

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 flag-controllable so the user can disable it for good.

Best regards from V.


#8

Quote:
I hope it is at least flag-controllable 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.

#9

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.

#10

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 non-integer 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.98918882e-08
(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 1E-7 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.103515625E-5
-54 Clear 1 .0078041 6.087161937E-5
-54 Set .998918882 7.80405376562E-3 6.08716193719E-5
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 LU-decomposition with row interchange is used, on the 48G and 49G

Cheers, Werner


#11

Hi, Werner:

Werner posted:

"? Changing the row order has no effect whatsoever, for LU-decomposition 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 HP-71B, which also uses LU-decomposition as far as I know.

Best regards from V.


#12

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 71-B 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 'floating-2'). 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


#13

Hi again, Werner:

Werner posted:

"Maybe the 71-B 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
    ill-conditioned matrices, even merely reordering the rows
    and columns can have a great impact on accuracy.

    For example, this reordering makes the HP-71B’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 1-2 digit integer coefficients, working with 12-digit outputs obtained from 15-digit internal arithmetic is certainly quite noticeable, isn't it ?

    My article fully discusses further manipulations with this particular matrix, comparing the HP-71B 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.


#14

Hi Valentin.

I was wrong, the 71-B 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 twelve-fold.

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 71-B 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


#15

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.

#16

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 TI-83+ and TI-95 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 12-digit 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 12-digit 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 12-digit floating point arithmetic.


Possibly Related Threads...
Thread Author Replies Views Last Post
  Equation Library/App for the Prime Harold A Climer 3 924 10-30-2013, 10:14 AM
Last Post: CompSystems
  Equation Library on the PRIME Harold A Climer 0 553 10-26-2013, 10:01 AM
Last Post: Harold A Climer
  Meltiple Equation Solver PRIME Vs. HP 50G Harold A Climer 5 1,044 10-07-2013, 05:11 PM
Last Post: CR Haeger
  EOT--TI N-Spire Equation Limit Matt Agajanian 2 723 09-22-2013, 12:37 PM
Last Post: Matt Agajanian
  Does Prime Have a Multiple Equation Solver? Norman Dziedzic 2 700 09-20-2013, 09:43 AM
Last Post: Norman Dziedzic
  Equation of the parabola given three points Gerson W. Barbosa 27 3,425 09-18-2013, 01:58 PM
Last Post: Gerson W. Barbosa
  HP 50g: Customize Your Equation Library Software49g 2 736 05-27-2013, 12:39 PM
Last Post: Software49g
  A very long HP-17BII equation Gerson W. Barbosa 22 3,093 04-19-2013, 12:37 AM
Last Post: Gerson W. Barbosa
  Web Equation Thomas Klemm 3 820 03-21-2013, 03:16 AM
Last Post: Nick_S
  Tangent's equation program for HP39gII Mic 22 3,115 03-01-2013, 11:14 AM
Last Post: Tim Wessman

Forum Jump: