Reputation
Top tag
Next privilege 50 Rep.
Comment everywhere
Badges
9
Newest
 Promoter
Impact
~1k people reached

  • 0 posts edited
  • 0 helpful flags
  • 4 votes cast
1d
awarded  Promoter
Aug
30
comment Looking for references on the complexity of computation of a basis transformation matrix
But could there be another approach computing $M$ via solving an equation system? This would sound like possibly reducing the running time to matrix multiplication which would be sufficient.
Aug
30
comment Looking for references on the complexity of computation of a basis transformation matrix
@ K. Miller: Reducing the running time to the one of matrix multiplication would deliver exactly the desired result: $O^{\sim}(n^\omega d)$.
Aug
30
comment Looking for references on the complexity of computation of a basis transformation matrix
@K. Miller: I'm looking for an asymptotic running time of $O^{\sim}(n^\omega d)$ where $d$ denotes the maximum of the degrees of the entries of the considered matrix. I'm not doing any implementation, instead I want to reason the asymptotic running time of another algorithm which uses this computation. There is no special structure to exploit. Do you know any references I may consider? We only have the parameters $n$ and $d$ from which the running time should depend on.
Aug
30
comment Looking for references on the complexity of computation of a basis transformation matrix
Yes, it would be sufficient to be able to compute $M = M_b^{-1}M_a$, but given the matrices $M_a, M_b$, say of degree $d$, computing the inverse $M_b^{-1}$ would be too expensive, see the link in my question. The matrices are defined over $K(x)$, we consider the vector space $V$ of dimension $n$ over $K(x)$.
Aug
30
revised Looking for references on the complexity of computation of a basis transformation matrix
deleted 1 character in body
Aug
30
revised Looking for references on the complexity of computation of a basis transformation matrix
added 143 characters in body
Aug
30
revised Looking for references on the complexity of computation of a basis transformation matrix
added 546 characters in body
Aug
30
asked Looking for references on the complexity of computation of a basis transformation matrix
Aug
26
asked Asymptotic running time for multiplying multivariate polynomials using Schönhage/Strassen
Feb
27
awarded  Curious
Feb
26
asked Representation Matrix computation time estimation
Dec
24
awarded  Tumbleweed
Dec
17
asked Determine the valuation of $\rho$ with $F = k(x,\rho)$ at the only place above $(\infty)$.
Nov
12
accepted Prime ideal $P$ in $R$ coprime to the conductor plus the localization $R_{P}$ is a DVR implies that $P$ is invertible
Nov
12
comment Prime ideal $P$ in $R$ coprime to the conductor plus the localization $R_{P}$ is a DVR implies that $P$ is invertible
The source is part of some lecture notes from my professor and therefore I wasn't sure if I'm allowed to put that here; besides it's written in german. And yes, $P + \mathcal{F} = B$ was used to show that $B_P$ is a DVR. Again, thank you very much!
Nov
12
comment Prime ideal $P$ in $R$ coprime to the conductor plus the localization $R_{P}$ is a DVR implies that $P$ is invertible
I thought about this before but I kind of scrapped that idea for no reason. Of course this is the answer, it's clear now! Thank you very much.
Nov
12
asked Prime ideal $P$ in $R$ coprime to the conductor plus the localization $R_{P}$ is a DVR implies that $P$ is invertible
Jul
31
awarded  Teacher
Jul
25
comment Why is every Divisor of the rational function field $K(x)$ over $K$ a principal divisor if $K$ is algebraically closed
So the statement is wrong as I suggested. Because the degree of a prime divisor is 1.