Re: Linear Algebra Challenge

How small do you require the determinant to be before you call it singular?

I don't. I minimize the distance using all but one of the matrix
elements, then go back and determine what the last element would have
to be in order for the matrix to be singular.

Have you found any whose determinant was exactly zero?

Since I'm using floating point, so I'll never be able to calculate one
exactly.

How DO you find your candidate singular matrices?

Let me use a 2x2 matrix for brevity. The 4x4 process is just the same,
only bigger.

Let
Original Matrix
mat0 = [[1+1/10000 1][2 2+1/10000]] (exact)
or
mat0 = [[1.0001 1][2 2.0001]] (floating point)

Pertibation Matrix (The 4x4 would have 'a' through 'p')
pert = [[a b][c d]]

Combined Matrix
mat = mat0 + pert

Determinant Polynomial as a function of a,b,c,d
detpoly(a,b,c,d) = det(mat)

This is the key step. Solve this polynomial for 'a' (or any variable)
as a function of the other variables. This _rational_ function takes
any values b,c,d and returns the value for 'a' that would make
det(mat)=0 (or nearly so if using floating point).
afunc(b,c,d) = solve(detpoly,a)

Distance Squared from Orginal
I used dist^2 instead of dist to make the derivatives easier.
dist2(a,b,c,d) = a^2 + b^2 + c^2 + d^2

Substitute afunc(b,c,d) in for 'a' in dist2. (4x4 would be d2('b' thru
'p') )
d2(b,c,d) = afunc(b,c,d)^2 + b^2 + c^2 + d^2

What I originally had in mind was to then take the gradient of d2 and
set it equal to zero and use MSLV on my 49g+ to solve the three
equations for b,c,d starting with initial guesses of b=0, c=0, d=0.
This root would be the location of the local minimum of d2 with respect
to each variable.
grad(d2)=0
ie: d/db(d2)=0, d/dc(d2)=0, d/dd(d2)=0

I can do these steps for a 2x2 with the following program, but it runs
out of memory for a 4x4. When I looked at the 15 enormous equations
(d/db thru d/dp), I could see why.

\<< PUSH -105. SF
[[ 1. 1. ][ 2. 2. ]] 2. IDN .0001 * +
[[ 'a' 'b' ][ 'c' 'd' ]] DUP2 + DUP DET \-> mat0 pert mat detpoly
\<< detpoly 'a' ISOL \-> aeq
\<< 'SQ(a)+SQ(b)+SQ(c)+SQ(d)' aeq SUBST [ 'b' 'c' 'd' ] SWAP OVER
DERIV SWAP
[ 0. 0. 0. ] MSLV AXL SWAP AXL SWAP = AXL NIP \-> vals
\<< aeq vals SUBST EVAL vals AXL + AXL 'vals' STO pert vals SUBST
"Pertibation" \->TAG mat0 "ORIG" \->TAG mat vals SUBST SIMPLIFY DUP
'mat' STO "Matrix" \->TAG SWAP mat DET "Det" \->TAG detpoly vals SUBST
EVAL "DetPoly" \->TAG mat mat0 - ABS "Dist" \->TAG
\>>
\>>
\>> POP
\>>


I switched over to Maxima to avoid the memory problem, but there isn't
anything like MSLV built in (or at least I couldn't find it). So I
decided to make one big monolithic equation f(b,c,d) whose zeros would
be only where grad(d2)=0. When f(b,c,d) is zero,the grad(d2) is zero
and d2 is at a minimum. (For a 4x4, it's f('b' thru 'p').)

f(b,c,d) = |grad(d2)|^2 = grad(d2) dot grad(d2)
= (d/db(d2))^2 + (d/dc(d2))^2 + (d/dd(d2))^2

I now took this function f(b,c,d) and used a multi-variable Newton's
Method routine to approximate b,c,d. (See below for explaination of
this method.) Once I found b,c,d (or until I got tired of waiting and
said, "close enough"), I took these values and calculated 'a' using
afunc(b,c,d) above. Remember, afunc(b,c,d) returns whatever value
would make the matrix (nearly) singular.
a = afunc(b,c,d)

Now that I have a,b,c,d, I can find the matrix.

What do you think? Do you see any flaws in my logic? (Well, other than
that it's bizaar.)


Maxima isn't giving you a good result here. When I take the numbers
you've posted just above and compute the determinant with 99 digit
arithmetic, I get -4.99762E-23 for the determinant. Maxima is giving you a
result about 4 orders of magnitude off (neglecting the sign error).

I had not noticed that, but you're right. I also got what you got when
I pasted what I posted back into Maxima and used arbitrary precision
floating point math set to 99 digits. However, I also got yet a
different number when I used regular floating point. After a little
experimenting, I figured out why. Maxima does not print all of its
digits, but has a few hidden "guard digits" just as some calculators
do. The results I posted were just copied and pasted from the output.
This did not include the guard digits.

I wonder just how close you will be able to get! :-)

As close as I'm willing to wait if I use arbitrary precision. At this
point, what's more important to me is knowing whether, in principle, my
method is valid.

Thoughts?

--------------------
Newton's Method
I don't recall ever seeing this in a text book, but a few years ago, I
derived:

Multi-Variable Newton's Method
(x,y,z,...)->(x,y,z..)-grad(f(x,y,z..))*f(x,y,z..)/|grad(f(x,y,z..))|^2

Notice if there is only one variable, this simplifies to the regular
single-variable Newton's Method:

x -> x - f(x)/f'(x)

pretty cool huh.

.

Relevant Pages

  • Re: Interesting math
    ... Floating point number represents a real number with 6 digits precision. ... Floating point numbers are denoted by the keyword float. ...
    (alt.usage.english)
  • Re: Gentler Decimal Floating-Point
    ... effectively change the radix of a decimal floating point ... under the heading "Logarithms all the time", ... logarithmic representation of numbers to be made workable for all the ... The middle digits are shifted only when the exponent, ...
    (comp.arch.arithmetic)
  • Re: Floating point subtraction rounding error (NOT display error)
    ... and apparently it's because floating point subtraction is having ... Notice that, to align both numbers at their decimal point, we had to discard the two less significant binary digits of 0.6. ... Note that this is the best result you can get with a limited precision of 53 bits, and it's not even Python who computes the value, but the underlying C math library. ...
    (comp.lang.python)
  • Re: Appoximating large numbers
    ... floating point number will correctly represent the first 15 digits of any ... give you the correct first 30 digits of any 16,000 digit number. ... looks like you're using an interpreted instead of a compiled language, ... I'm not familiar with Ruby ...
    (sci.math.num-analysis)
  • Re: Linear Algebra Challenge
    ... precision, maybe you could turn on higher precision ... it gives me about 5 extra digits. ... "Maxima is also giving only about 11 correct digits for dist. ... With such complex equations, I doubt I could actually get the full 16 ...
    (comp.sys.hp48)