I guess it can be possible to get a smaller example and it may be possible
that this code has other problems. My goal is to compute the Fitting ideals
of the "abelian" Alexander matrix of a finitely presented group. If you
execute and hold the two last paragraphs, for me the execution time of the
first of those paragraphs is quite fast while the last one takes really
long (I have no patience to say how long if it ends).
I try to provide you a shorter code starting directly with the matrix
(print out the list of coefficients and recreate it) but in that case both
codes were fast.
So maybe the problem is not on Laurent polynomials but I still share it
just in case.
Thanks, Enrique.
El miércoles, 31 de mayo de 2023 a las 15:24:46 UTC+2, Kiran Kedlaya
escribió:
> I wrote that code into the Sage library and it is supposed to be doing
> exactly what you proposed (clear denominators and do the computation in the
> polynomial ring). It is possible the regression was triggered by an update
> to Singular; it would indeed be helpful to identify a minimal example of
> the problem and then post it to a ticket.
>
> I believe there are also some upstream bugs with minimal associated
> primes, e.g., https://github.com/sagemath/sage/issues/29671.
>
> Kiran
>
> On Monday, May 29, 2023 at 8:53:59 PM UTC-7 Travis Scrimshaw wrote:
>
>> Dear Enrique,
>> I am having a bit of trouble understanding exactly what computations
>> are slow and fast from your description. As Nils said, can you give us some
>> explicit code (with some comments about which parts are slow)?
>>
>> Best,
>> Travis
>>
>> On Tuesday, May 30, 2023 at 3:28:39 AM UTC+9 Nils Bruin wrote:
>>
>>> Dear Enrique,
>>>
>>> From what you write I get the impression you may be talking about a
>>> regression in performance relative to earlier versions of sage. If you want
>>> to make an actionable item out of this, you'll probably have to file a
>>> ticket with explicit code on it that can be profiled; preferably with an
>>> indication why you think the performance could be significantly improved.
>>> That doesn't guarantee someone will work on it but it at least gives them a
>>> place to start if they want to, including you yourself! You could file it
>>> as an "enhancement" or even as a "bug" if you can convincingly show it's a
>>> regression. In the latter case you would probably end up identifying a
>>> version in which performance was significantly better. A git diff on some
>>> of the relevant files could then perhaps very quickly show what's happening.
>>>
>>>
>>>
>>> On Monday, 29 May 2023 at 09:07:07 UTC-7 enriqu...@gmail.com wrote:
>>>
>>>> Some time ago I had some computations on ideals in Laurent polynomial
>>>> rings, namely looking for minimal associated primes. Basically, I
>>>> converted
>>>> any generator into a polynomial, study the ideal in the polynomial ring,
>>>> and forget the prime ideals containing monomials. From some time ago, it
>>>> is
>>>> much easier since it can be done directly in the ring of Laurent
>>>> polynomials.
>>>> Yesterday these computations on an ideal with 80 generators were really
>>>> slow, but for some reason I checked that if the generators were converted
>>>> to elements in the associated polynomial ring, and then the ideal in the
>>>> Laurent polynomial ring is constructed, then those computations were
>>>> solved
>>>> really fast.
>>>> I checked the code but I was not able to isolate the reason. Best,
>>>> Enrique.
>>>>
>>>
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-devel+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/sage-devel/ae1e10b1-6343-488a-93a6-87213d7e2be2n%40googlegroups.com.
# Return a ring of Laurent polynomials together with an ideal,
# the images of the generators of the group in the abelianization
# and the abelianization itself. The group algebra of the group
# is the quotient of the ring by the ideal
def abelianization(G):
from sage.groups.finitely_presented import wrap_FpGroup
hom_libgap_ab = libgap(G).MaximalAbelianQuotient()
ab_libgap = hom_libgap_ab.Range()
hom_ab_fp = ab_libgap.IsomorphismFpGroup()
ab0 = hom_ab_fp.Range()
hom_sim = ab0.IsomorphismSimplifiedFpGroup()
ab = wrap_FpGroup(hom_sim.Range())
R = LaurentPolynomialRing(QQ, ab.gens())
ideal = []
for a in ab.relations():
a_T = a.Tietze()
a_S = Set(a_T)
if a_S.cardinality() == 1:
j = a_T[0]
m = len(a_T)
ideal.append(R.gen(j - 1) ** m - 1)
images = []
for f in G.gens():
f0 = hom_libgap_ab.Image(f)
f1 = hom_ab_fp.Image(f0)
f2 = hom_sim.Image(f1)
L = f2.UnderlyingElement().LetterRepAssocWord()
p = R.one()
for a in L:
if a > 0:
p *= R.gen(a - 1)
elif a<0:
p /= R.gen(-a - 1)
images.append(p)
return R, ideal, images, ab
# The Alexander matrix of the group over the group algebra
# of the abelianization
def abelian_alexander_matrix(G, abelianized=None):
if abelianized is None:
R, ideal, images, ab = abelianization(G)
else:
R, ideal, images, ab = abelianized
A = G.alexander_matrix(im_gens=images)
return A, R, ideal
# If there are units the matrix can be reduced.
def simplify_matrix(A):
n, m = A.dimensions()
if 0 in (n, m):
return A
R = A.base_ring()
simpli = True
while simpli:
i, j = [0, 0]
unidad = False
while not unidad and i < n and j < m:
p = A[i, j]
unidad = p.is_unit()
if unidad:
A.swap_rows(0, i)
A.swap_columns(0, j)
for i in range(1, n):
A.add_multiple_of_row(i, 0, -A[i, 0] * p ** -1)
A = A.delete_rows([0]).delete_columns([j])
n, m = A.dimensions()
else:
if j < m - 1:
j += 1
else:
i += 1
j = 0
simpli = unidad
return A
# Mutltiply a Laurent polynomial by a unit
# to obtain a polynomial
def Laurent2Pol(p):
S = p.parent().polynomial_ring()
if p == 0:
return p
R = p.parent()
m = R.ngens()
if m > 1:
L = p.exponents()
else:
return p.polynomial_construction()[0]
minimo = [min(a[j] for a in L) for j in range(m)]
return S(prod(R.gen(j)^-minimo[j] for j in range(m))*p)
# A group and its derived subgroup
from sage.groups.finitely_presented import wrap_FpGroup
F=FreeGroup(3)
L=[(1,2,1,-2,-1,-2),(2,3,2,-3,-2,-3),(1,3,1,-3,-1,-3),2*(1,2,3)]
G=F/L
K=wrap_FpGroup(libgap(G).DerivedSubgroup().IsomorphismFpGroup().Range())
K=K.simplified()
A, R, ideal = abelian_alexander_matrix(K)
L0 = [Laurent2Pol(p) for p in A.minors(3)]
J0 = R.ideal(L0)
LJ0 = J0.minimal_associated_primes()
LJ0
%%time
A, R, ideal = abelian_alexander_matrix(K)
J1 = R.ideal(A.minors(3))
LJ1 = J1.minimal_associated_primes()
LJ1
