#6441: [with patch, needs work] Charpoly (plus adjoint and det)
----------------------------+-----------------------------------------------
Reporter: spancratz | Owner: somebody
Type: defect | Status: new
Priority: minor | Milestone: sage-4.1.2
Component: linear algebra | Keywords: charpoly, division-free
Reviewer: | Author: Sebastian Pancratz
Merged: |
----------------------------+-----------------------------------------------
Comment(by ylchapuy):
Hi Sebastian,
my last remark might have been unclear, but look at this:
{{{
def charpoly_divfree(M):
n = M.ncols()
R = M.base_ring()
S = PolynomialRing(R, 'x')
F = [ R(0) for i in xrange(n) ]
a = [[R(0) for i in xrange(n)] for p in xrange(n-1)]
A = [ R(0) for i in xrange(n) ]
F[0] = - M[0, 0]
for t in xrange(1,n):
for i in xrange(t+1):
a[0][i] = M[i, t]
A[0] = M[t, t]
for p in xrange(1, t):
apm=a[p-1]
for i in xrange(t+1):
s = R(0)
for j in xrange(t+1):
s += M[i, j] * apm[j]
a[p][i] = s
A[p] = a[p][t]
atm=a[t-1]
for j in xrange(t+1):
A[t] += M[t, j] * atm[j]
for p in xrange(t+1):
for k in xrange(p):
F[p] -= A[k] * F[p-k-1]
F[p] -= A[p]
F.reverse()
F.append(R(1))
return S(F)
}}}
this works, with smaller F,A,a using n**2 memory instead of n**3...
Yann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/6441#comment:11>
Sage <http://sagemath.org/>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en
-~----------~----~----~----~------~----~------~--~---
