Calculation of determinant on HP-15C

[NumberJack]

Hi everyone,

I computed the determinant of a 4x4 matrix on the HP-15C. All coefficients of the matrix are small integers. I know the determinant is 0, but the HP-15C returns "2.1000 -10" in the display, which is a very small number but not 0.

So my question is whether the HP-15C calculates always a numerical approximation of the determinant even when the coefficients of the matrix are small integers? Is there a way to get the "correct" determinant?

Thanks!

[Dave Britten]

(03-10-2021 09:09 AM)NumberJack Wrote:  Hi everyone,

I computed the determinant of a 4x4 matrix on the HP-15C. All coefficients of the matrix are small integers. I know the determinant is 0, but the HP-15C returns "2.1000 -10" in the display, which is a very small number but not 0.

So my question is whether the HP-15C calculates always a numerical approximation of the determinant even when the coefficients of the matrix are small integers? Is there a way to get the "correct" determinant?

Thanks!

I ran into that on the 42S a while back. I'm assuming it's the same symptom on the 15C.

https://www.hpmuseum.org/forum/thread-13830.html

[JMBaillard]

Hi NumberJack,

I've written programs to compute determinants on the webpage: http://hp41programs.yolasite.com/determinant.php for the HP41.

It should give exact results without roundoff errors
for determinants of order 3 , 4 , 5 if the coefficients are not too large.

But I don't know if these programs can run on an HP15C...

Best regards,
JM.

[John Keith]

(03-10-2021 09:09 AM)NumberJack Wrote:  So my question is whether the HP-15C calculates always a numerical approximation of the determinant even when the coefficients of the matrix are small integers?

This is true. AFAIK all HP calculators before the HP49 used numeric methods for matrix operations.

[Thomas Okken]

Only if you mean "numeric" as opposed to "symbolic." The algorithms are not approximations in the sense of numerical iterative methods; in infinite precision, they would be exact. But with finite precision, you will get results that aren't exact even if the algorithm is exact in principle. This is essentially the same phenomenon as what causes 1 ENTER 3 / 3 * 1 - to return a nonzero result.

[C.Ret]

This is a normal and common fact on any calculators to get approximation on most arithmetic operations.

Fortunately, the HP-15C have a rounding function. Select the expected precision of your specific application by using the appropriate f FIX n command, compute your 4x4 matrix determinant and then evacuate discrepancies by pressing g RND.

You will see your 2.1 E-10 result being transform in a zero.

May I suggest you to give us a printout of your specific matrix. Perhaps, same expert of the forum may found a twisted way or a smart arrangement that make the computation straightforward !?

Here is an exemple of a matrix 4x4 composed of sixteen small integers whose determinant is -3276. Despite using a LU decomposition, the HP-15C give the correct and accurate integer value of the determinant.

\( \begin{bmatrix}4&7&7&8\\ 5&-1&2&-4\\ 3&12&-5&6\\ 1&4&7&2 \end{bmatrix}=-3276 \)

[Werner]

The 15C, as well as the 42S, have one peculiarity not mentioned before: they will alter a degenerate factorisation (ie. DET=0) by a small amount (1e-12 in the case of the 42S).
Take the obvious case

[[ 1 1 0 ]
[ 1 1 0 ]
[ 0 0 1 ]]

and compute its determinant.. the 42S returns -2e-12.
This is obviously not a consequence of roundoff here.
See the 15C Advanced Functions Handbook pg 117-118 for an explanation.

Cheers, Werner

[J-F Garnier]

(03-10-2021 05:47 PM)Werner Wrote:  The 15C, as well as the 42S, have one peculiarity not mentioned before: they will alter a degenerate factorisation (ie. DET=0) by a small amount (1e-12 in the case of the 42S).
Take the obvious case

[[ 1 1 0 ]
[ 1 1 0 ]
[ 0 0 1 ]]

and compute its determinant.. the 42S returns -2e-12.

I got 1E-12 for this matrix on the 42S, same on the 75C Math ROM, the 71B Math ROM 1A and the 28C.

Starting from the 28S, the DET is no more using the altered pivots but the real ones (possibly null) and the DET is exactly zero (for these cases, without rounding errors).

On the 71B Math ROM 2B, I aligned the algorithm to the 28S.

The 42S has another quirk, that I didn't find in any other Saturn-based machines:
Try:
[[ 1E10 0 0 ]
[ 0 0 0 ]
[ 0 0 1E10 ]]
DET is 1E-492. This is the result of 1E10 x 1E-512 x 1E10.

J-F

[Werner]

(03-10-2021 08:36 PM)J-F Garnier Wrote:  I got 1E-12 for this matrix on the 42S, same on the 75C Math ROM, the 71B Math ROM 1A and

Yes it’s 1e-12, the -2e-12 was from another matrix

Quote:The 42S has another quirk, that I didn't find in any other Saturn-based machines:
Try:
[[ 1E10 0 0 ]
[ 0 0 0 ]
[ 0 0 1E10 ]]
DET is 1E-492. This is the result of 1E10 x 1E-512 x 1E10.

This is the same adjustment at work: (guessing) it is proportional to the max value of the row, which is zero here, resulting in the smallest (denormalised) number that can be represented, which I thought was 1e-511, but my thoughts are becoming less and less reliable ;-).
Should be the same in the 48S? Can’t verify myself anymore.

Cheers, Werner

[John Keith]

I don't have a 48S handy but I do recall reading that the accuracy of matrix operations was improved in the 48G relative to the 48S. I don't recall any other details off hand.

[Werner]

Yes, that’s why I said 48S ;-)
The 48S used 15-digit precision only in dot products, like the 42S; the 48G and up expand the matrix first to 15 digits and do all calculations in extended precision.
Cheers, Werner

[Didier Lachieze]

I checked on my 48SX and DET returns 0 for

[[ 1E10 0 0 ]
[ 0 0 0 ]
[ 0 0 1E10 ]]

as well as for

[[ 1 1 0 ]
[ 1 1 0 ]
[ 0 0 1 ]]

[Joe Horn]

(03-11-2021 07:31 PM)Didier Lachieze Wrote:  I checked on my 48SX and DET returns 0 for

[[ 1E10 0 0 ]
[ 0 0 0 ]
[ 0 0 1E10 ]]

So does the HP-71 with the Math ROM.

[Valentin Albillo]

(03-10-2021 09:09 AM)NumberJack Wrote:  I computed the determinant of a 4x4 matrix on the HP-15C. All coefficients of the matrix are small integers. I know the determinant is 0, but the HP-15C returns "2.1000 -10" in the display, which is a very small number but not 0.

This happens because, though computing a determinant is an operation which theoretically requires just multiplications and additions/subtractions but no divisions, the algorithm used in the HP-15C and most other calculators/pocket computers (if not all) does use divisions by pivots, and those divisions very rarely come out exact but usually introduce very small rounding/truncation errors which, as the algorithm requires a large number of arithmetic operations, eventually delivers non-exact results even when all the matrix elements are small integers.

Quote:Is there a way to get the "correct" determinant?

The only way to avoid this (apart from using exact rational arithmetic or symbolic results) would be to use an algorithm that does not use divisions. There are a number of them but whether they would fit in the HP-15C's program memory and still allow space for a 4x4 matrix is quite another question, and I would say that fitting both the program and the 4x4 matrix and other ancillary variables plus doing the computation in reasonable times would be quite diffcult if not impossible.

For models such as the HP-42S upwards (HP-71B and the RPL models) it's quite possible and not particularly difficult. For example, have a look at Example 5 (pages 8-9) in this article (PDF) of mine, which demonstrates the algorithm by exactly computing the determinant of a 7x7 matrix with all small integer elements.

V.

[Werner]

(03-11-2021 07:31 PM)Didier Lachieze Wrote:  I checked on my 48SX and DET returns 0 for

[[ 1E10 0 0 ]
[ 0 0 0 ]
[ 0 0 1E10 ]]

as well as for

[[ 1 1 0 ]
[ 1 1 0 ]
[ 0 0 1 ]]

Didier, does the HP48S also use flag -54, tiny element?
If it is clear, set it and try again, please.
Certainly on the 48G and up, when flag -54 is clear (as I believe it is, by default), then an extra check is performed before the determinant is calculated: to see whether all matrix elements are integer - for then, the result must be integer, too, and it is *changed* to the nearest integer
(the actual test is not for integers, but the explanation will do here)

Cheers, Werner

[Didier Lachieze]

(03-12-2021 08:26 AM)Werner Wrote:  Didier, does the HP48S also use flag -54, tiny element?

No, flag -54 is unused on the 48SX.

[Valentin Albillo]

(03-12-2021 08:26 AM)Werner Wrote:  Certainly on the 48G and up, when flag -54 is clear (as I believe it is, by default), then an extra check is performed before the determinant is calculated: to see whether all matrix elements are integer - for then, the result must be integer, too, and it is *changed* to the nearest integer

This was discussed at length in several threads in the old MoHPC forum decades ago, and I remember that someone actually produced a (small) matrix where using that "cheating" flag resulted in the integer determinant being computed with an error of one full unit, so the cheating didn't pay that time as you got a much worse (a full unit) incorrect result by using it than without.

The general conclusion was that tweaking the results to make them conform to (integer) expectations (and to try and mimic greater accuracy that actually wasn't there) was a shoddy work which might embarrassingly backfire. Examples where this was done for other non-HP calculators were also discussed as well.

Regards.
V.

[Werner]

I know. I was in those discussions as well.
Cheers, Werner

[Werner]

(03-12-2021 07:05 PM)Valentin Albillo Wrote:  This was discussed at length in several threads in the old MoHPC forum decades ago, and I remember that someone actually produced a (small) matrix where using that "cheating" flag resulted in the integer determinant being computed with an error of one full unit, so the cheating didn't pay that time as you got a much worse (a full unit) incorrect result by using it than without.

Actually, I was the one who gave that example, and a few others.
They all started from your own 7x7 matrix AM1, constructed to have a large condition number and a DET=1:

58 71 67 36 35 19 60
50 71 71 56 45 20 52
64 40 84 50 51 43 69
31 28 41 54 31 18 33
45 23 46 38 50 43 50
41 10 28 17 33 41 46
66 72 71 38 40 27 69

On a 48G and up, DET will produce (in approx mode for 49G and up):
F -54 C (default): 1.0
F -54 S : 0.999945522778

Now, if you take AM1*4, the true determinant will be 4^7 = 16384. Now the results of DET are:
F -54 C : 16383.0
F -54 S : 16382.5548739

so the cheat failed here, you could say. But, with a condition number of 6.6e10, both results are equally wrong or right. The exact integer however, may give the feeling that the answer is correct. The reason why my flag -54 is always set, to bypass the fiddling ;-)

Quote:The general conclusion was that tweaking the results to make them conform to (integer) expectations (and to try and mimic greater accuracy that actually wasn't there) was a shoddy work which might embarrassingly backfire. Examples where this was done for other non-HP calculators were also discussed as well.

I wouldn't call it shoddy work - it is quite well done, and will deliver correct results in all but very badly conditioned matrices, where the result can't be trusted anyway. But the same goes for simply solving a set of linear equations: if you don't estimate the condition of your matrix, you don't know to what extent you can trust your results.

Cheers, Werner