Unexpected result calculating the determinant of a singular matrix (42S)

[Paul Dale]

I believe that the 15C (and presumably) 42S use the Doolittle algorithm.


Pauli

[Thomas Okken]

(10-22-2019 06:12 AM)Werner Wrote:  the 42S uses a*b-c*d when calculating the determinant of a 2x2 system, as you can see when you calculate the determinant of

1 2
3 1

and

1 2 0
3 1 0
0 0 1

The former returns -5 exactly, the latter -5.00000000001

So does that mean that the difference between the 42S and the 48G is that the former performs the calculation using only 12 digits? The number -5.00000000001 differs from the exact result in the 12th digit, while you'd expect to get the exact result if it performed the calculation in 15 digits and only rounded to 12 at the end.

The use of 15 digits would also explain how the 48G is able to get the exact result for Dave's example, regardless of the state of flag -54. That is, unless that's just a coincidence.

[Werner]

Yes; the 48S used the same algorithm as the 42S (so only dot products accumulated with 15 digits), but the 48G and onwards expand the whole matrix to 15 digits, perform all calculations and then truncate or round back to 12 digits (don't remember which. I think it truncates).

Cheers,
Werner

[Valentin Albillo]

.
Hi, Werner:

(10-22-2019 06:12 AM)Werner Wrote:  ? of course the cheat works. With Flag -54 clear, the 48GX returns 1 exactly, with Flag -54 set it returns .999945522778.

Well, I don't own any breed of HP48 so I couldn't check it myself but the only reason it works here is because AM#1 is way too nice and the calc returns a determinant, 0.9999455..., which is close enough to 1 to make the cheat work.

But try instead with AM#7, a matrix of the same dimensions (7x7) and similarly-sized integer elements, as detailed in my article

Mean Matrices, under "Can it get any worse ?"

and see how the 48 fares, with or without cheat. Can't check it myself but I very much doubt it will deliver the goods this time.

Regards.
V.

[Werner]

(10-23-2019 04:50 AM)Valentin Albillo Wrote:  But try instead with AM#7, a matrix of the same dimensions (7x7) and similarly-sized integer elements, as detailed in my article

Mean Matrices, under "Can it get any worse ?"

Still works..
This time the condition number is about 7e12, and the determinant can be expected to be correct to about 2 digits: .998918882 with F-54 Set.
With F-54 Clear, it's 1 exactly, of course.
A 7x7 matrix with integer elements less than 100 and determinant 1 will always have at least 1 digit correct when the calculations are done with 15 digits, and so the rounding will work.

Now, Valentin, I have always wondered how you created these matrices, and I've asked you once before (a very long time ago, admittedly). Can you shed some light on this?

Cheers, Werner

[Valentin Albillo]

.
Hi, Werner:

(10-23-2019 07:01 AM)Werner Wrote:  

(10-23-2019 04:50 AM)Valentin Albillo Wrote:  But try instead with AM#7, a matrix of the same dimensions (7x7) and similarly-sized integer elements, as detailed in my article

Mean Matrices, under "Can it get any worse ?"

Still works..

Ok, I give up.

Quote:A 7x7 matrix with integer elements less than 100 and determinant 1 will always have at least 1 digit correct when the calculations are done with 15 digits

I can't try and find a counterexample to what you state because I don't have an HP48-whatever to check if my attempts work or not so I'll take your word for it.

Quote:Now, Valentin, I have always wondered how you created these matrices, and I've asked you once before (a very long time ago, admittedly). Can you shed some light on this?

I don't remember you asking me about this but you're right, it's been an awfully long time since then. As for shedding some light, it's complicated to honor your request because I recently suffered a couple of computer disasters in quick succession and haven't still fully recovered from them, right now my main computing device is a tablet.

One of the machines which suddenly died had the indexes to all my materials in the many external HDD drives I own which hold my archived materials, so to say, and thus makes it extremely difficult to find old, archived files without looking through them all, many terabytes.

From memory (and it's been a looooong time) I think I started from a number of suitable matrices (i.e., low dimensions, say 7x7, small integer elements, determinant 1) and defined a series of matrix manipulations that would preserve the determinant of the matrices being created anew by the process. Then I created a program which (1) performed the determinant-preserving manipulations, (2) implemented a genetic-like algorithm that created new generations of matrices and selected the best ones according to some criteria, and (3) after letting it run for a long while it would finally output the best matrices found.

The process could be either fully automatic, running unattended, or I could use it interactively and somewhat direct "evolution" to the most promising branches.

Sorry for the vagueness but I don't recall many details right now. I remember that the program was mid-sized and moderately complex and it finally produced a number of 7x7 AM matrices, from #1 to #7, as well as some others of various dimensions and element sizes.

Regards.
V.

[Werner]

(10-23-2019 11:06 PM)Valentin Albillo Wrote:  

Quote:A 7x7 matrix with integer elements less than 100 and determinant 1 will always have at least 1 digit correct when the calculations are done with 15 digits

I can't try and find a counterexample to what you state because I don't have an HP48-whatever to check if my attempts work or not so I'll take your word for it.

Suppose you calculate the determinants using Cramer's rule. The intermediate products would then be no larger than 100^7 = 1e14, the final result being 1 - so you'll lose at most 14 digits. I think ;-)

Cheers, Werner

[Valentin Albillo]

(10-24-2019 06:34 AM)Werner Wrote:  

(10-23-2019 11:06 PM)Valentin Albillo Wrote:  I can't try and find a counterexample to what you state because I don't have an HP48-whatever to check if my attempts work or not so I'll take your word for it.

Suppose you calculate the determinants using Cramer's rule. The intermediate products would then be no larger than 100^7 = 1e14, the final result being 1 - so you'll lose at most 14 digits. I think ;-)

Not necessarily. For a 7x7 matrix with 2-digit integer elements each individual intermediate product would be no longer than 7x2 = 14 digits, that's correct, but to compute the determinant you're adding up many such products and thus the result can wildly exceed 14 digits, so if you're using just 15 digits for the intermediate terms and final result you're likely to lose them all and then some.

Regards and have a nice weekend.
V.

[Werner]

Ah yes indeed, you are right. So it is not impossible to have a 7x7 with integer elements < 100 and a condition number > 1e15, so that the cheat would not work.
Here's a 2x2 for which it fails:

Code:

[[ 49'999'999 49'999'998 ]
 [ 50'000'000 49'999'999 ]]

Cheers, Werner