[Sherjil, I'm CC-ing you because in my head you are the "linear algebra
expert" :-)]
One last update for today: I tried to implement code which finds a
"nice" solution.
Problem statement: let Ax=0 be a homogeneous system with non-trivial
solutions. Find a non-trivial solution with maximal number of zeros in
it. I'd be very happy if someone could come up with and post a good
algorithm to do that. Or any sign that anyone is reading my musings at
all ^^.
My attempt is pasted below. It seems to work, but it is prohibitively
slow (see also my trigsimp branch for those who do not like to copy and
paste). You can test it with
dic = S('{c1: -25*d2/22 - 14*d3/55 + 48*d4/55 + 4*d5/11 - 3*d6/11, c2:
75*d2/88 + 49*d3/660 - 14*d4/55 - 7*d5/66 + 7*d6/88, c6: 29*d2/44 +
109*d3/330 - 23*d4/55 - 17*d5/66 + 25*d6/44, c3: 5*d2/44 + 911*d3/1650 -
59*d4/550 - 17*d5/165 + 17*d6/220, c5: -d2/2 - 4*d3/15 + d4/5 + 2*d5/3,
c0: -135*d2/88 - 103*d3/132 + 9*d4/11 + 25*d5/33 + 5*d6/88, d0:
-125*d2/44 - 801*d3/550 + 391*d4/275 + 72*d5/55 + 59*d6/220, c4:
-35*d2/44 - 224*d3/825 + 256*d4/275 + 31*d5/165 - 31*d6/220, d1:
-117*d2/44 - 35*d3/66 + 20*d4/11 + 25*d5/33 - 25*d6/44}')
syms = symbols('c0:7') + symbols('d0:7').
There is a solution with only six non-zero entries.
[Note the dic is the output from solve for the underdetermined
homogeneous system. Hence the problem findsol attempts to solve is to
find choices for the free symbols - those not determined by dic - so as
to make as many of the symbols zero, *without* making all of them zero]
--------------------------------------
def findsol(dic, syms):
from itertools import combinations
free = [x for x in syms if not x in dic]
poss = []
for keys in combinations(dic.keys(), len(free)):
#print keys
s = solve([dic[a] for a in keys])
if not all(v == 0 for _, v in s.iteritems()):
poss.append(s)
if not poss:
print "not working"
return findsol2(dic, syms)
poss.sort(key = lambda x: len([y for y in x.itervalues() if y ==
0]), reverse=True)
s = poss[0]
nfree = [(x, 1) for x in free if not x in s]
determined = dict(nfree)
for k, v in s.iteritems():
determined[k] = v.subs(determined)
for k, v in dic.iteritems():
determined[k] = v.subs(determined)
return determined
def findsol2(dic_, syms):
dic = dic_.copy()
forceone = max(dic.keys(), key=lambda x: len(dic[x].free_symbols))
determined = {}
while len(determined) != len(syms) and dic:
if forceone in dic and len(dic[forceone].free_symbols) == 1:
x = list(dic[forceone].free_symbols)[0]
if dic[forceone].subs(x, 0) == 0:
determined[x] = 1
else:
determined[x] = 0
else:
newsym = min(dic.keys(), key=lambda x:
len(dic[x].free_symbols))
x = list(dic[newsym].free_symbols)[0]
if len(dic[newsym].free_symbols) > 1:
determined[x] = 0
else:
determined[x] = solve(newsym)[0]
delete = []
for k in dic:
dic[k] = dic[k].subs(determined)
if not dic[k].free_symbols:
determined[k] = dic[k]
delete.append(k)
for k in delete:
del dic[k]
for x in syms:
if x not in determined:
determined[x] = 0
return determined
--
You received this message because you are subscribed to the Google Groups
"sympy" 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/sympy?hl=en.
