Questions tagged [computer-algebra]
Using computer-aid approach to solve algebraic problems. Questions with this tag should typically include at least one other tag indicating what sort of algebraic problem is involved, such as ac.commutative-algebra or rt.representation-theory or ag.algebraic-geometry.
368
questions
1
vote
1
answer
107
views
Finding a characteristic for which the zero-locus of an ideal is not empty
I have a set of polynomials $f_1, \dots, f_m \in \mathbb{Z}[x_1, \dots, x_n]$ and I am interested in finding if these polynomials have a common root inside either $\mathbb{C}[x_1, \dots, x_n]$ or $\...
1
vote
1
answer
332
views
Is this algorithm for primary decomposition correct?
I've written some code for Sage to compute radical ideals and primary decompositions over $\overline{Q}$ (the field of algebraic numbers), and I'm not sure if it's right.
Since Singular (the ...
5
votes
0
answers
111
views
Computing centralizers of finite sets in right angled Artin groups (RAAGs) / partially commutative groups / graph groups
This question concerns right angled Artin groups (RAAGs), also called partially commutative groups or graph groups.
A student of mine, Adi Ben-Zvi, needs for an algorithm in RAAGs, a subalgorithm ...
4
votes
0
answers
94
views
Compute equalizer of maps of polynomial rings, perhaps using Gröbner bases
Suppose that $k$ is a field and I have two ring homomorphisms
$$
\phi, \psi :k[x_1,...,x_m] \to k[y_1,...,y_n].
$$
How can I use Gröbner bases (or other computational tools) to compute the subring of ...
3
votes
2
answers
354
views
Alternate descriptions of finite fields
The finite field of order $p^n$ is isomorphic to $(\mathbb Z/p \mathbb Z)[X]/(P)$, where $P$ is an irreducible polynomial in $(\mathbb Z/p \mathbb Z)[X]$ of degree $n$. This describes every finite ...
4
votes
0
answers
410
views
Computing the volume of intersection between a ball and a box
$C$ is the set of vectors which are coordinate-wise less than $\overline{c}\in [-1,1]^d$ and greater than $\underline{c}\in [-1,1]^d.$ Is there a procedure not exponentially complex in $d$ that ...
0
votes
0
answers
32
views
Limit/Expansion Problems for Benchmarking
I am interested in collections of ‘interesting’ problems involving limits and/or asymptotic expansions of univariate real-valued functions. The purpose is to test a particular algorithm that I ...
3
votes
1
answer
231
views
Finding all selforthogonal indecomposable modules
Given a finite dimensional algebra $A$ with finite global dimension such that there are only finitely many basic tilting modules. Then every selforthogonal indecomposable module $M$ (that is a module ...
6
votes
1
answer
141
views
Software for computing equivariants
If $\Gamma$ is a finite group with action on two vector spaces $\mathbb R^n$ and $\mathbb R^m$ denoted by $\gamma_n$ and $\gamma_m$ respectively, the fundamental equivariants are the polynomials $f: \...
11
votes
1
answer
470
views
Representing field elements in a computer
I'm wondering if there is existing terminology to describe fields $F$ with the properties below. I don't have a completely precise description of the concept I have in mind, but hopefully this will be ...
3
votes
0
answers
96
views
Deterministic procedure to find irreducible polynomials
In $\Bbb F_q[x_1,\dots,x_n]$ given $d_1,\dots,d_n\in\Bbb N$ is there a deterministic $O(poly(nd\log q))$ algorithm to find an irreducible polynomial with $d=\max_{i\in\{1,\dots,n\}}d_i$ and $d_i=deg(...
1
vote
0
answers
35
views
Grobner basis of the toric ideal $I_{A_P}$ with respect to $<_{rev}$ consists of those binomials $t_αt_β − t_{α\cap β} t_{α\cup β}$
I try to understand the proof of the Theorem. 10.1.3.(page 185) from ''Monomial Ideals'' by Herzog & Hibi.
The reduced Grobner basis of the toric ideal $I_{A_P}$ with respect
to $<_{rev}$ ...
5
votes
2
answers
500
views
What are the most general methods for solving equations in closed form with Lambert W?
What are the most general methods for solving equations with help of Lambert W function or with a generalization of Lambert W function in closed form?
I gave a method in MSE here.
Which algorithms ...
3
votes
1
answer
510
views
Generalized Newton Identities
I learnt a lot of new words (Hall-Littlewood, Jack and Macdonald polynomials) but unfortunately everything I dug up is written without a single example and I still don't know the answer to a very ...
11
votes
1
answer
540
views
How do computer algebra packages like Sagemath implement rank of a matrix
I am not sure if this is the right place to ask this question, but I believe there will be people here who do computations on computer algebra packages like Sage in their work.
I have been using ...
26
votes
5
answers
6k
views
Minimal polynomial of cos(π/n)
I know that $\cos(\pi/n)$ is a root of the Chebyshev polynomial $(T_n + 1)$, in fact it is the largest root of that polynomial, but often that polynomial factors. For example, if $n = 2 k$ then $\cos(\...
23
votes
2
answers
1k
views
What is currently feasible in invariant theory for binary forms?
When Paul Gordan became a professor in 1875 he could show the binary form in any degree has some finite complete system of (general linear) invariants, but he could not actually give a complete system ...
6
votes
1
answer
1k
views
Computing kernels of maps of modules over a finitely presented algebra
I have the following problem: I have an associative (noncommutative) algebra $A$ defined over a rational function field $k = \mathbb{Q}(\delta, \lambda)$. $A$ is given by a presentation in terms of ...
2
votes
1
answer
257
views
Memory usage of Gröbner basis computation
I've been calculating some Gröbner bases in preparation for finding non-commutative Hilbert series (and, once I recreate that, characters of group actions). Specifically, I've been using the ...
8
votes
6
answers
3k
views
Computation of a minimal polynomial
It is relatively easy (but sometimes quite cumbersome) to compute the minimal polynomial of an algebraic number $\alpha$ when $\alpha$ is expressible in radicals. For example, the simple query
"...
3
votes
0
answers
103
views
Can one do better than using general purpose determinant algorithms when using the Fisher-Kasteleyn-Temperley method for perfect matchings?
Questions.
(numerical.generalPfaffian) Is it proved anywhere that in general it is not easier0 to calculate the determinant (over $\mathbb{Q}$) of the skew-symmetric signed adjacency matrix defined ...
3
votes
1
answer
234
views
Explicit endomorphisms of Jacobians of genus $2$ and the Theta divisor
I hope this question is good to be here.
Let $J$ be the Jacobian of a hyperelliptic curve $H$ of genus $2$ given by $y^2 = x^5 + h$.
I was calculating an explicit formula in Mumford coordinates of $[...
3
votes
0
answers
163
views
Explicit roots in algebraic extention of Q with roots
Denis Bouhineau in "Solving Geometrical Constraint System Using CLP Based on Linear Constraint Solver" gave a method to find explicit square root in algebraic extention of Q with square roots. For ...
2
votes
2
answers
365
views
Computer algebra for calculating curvature when the tensor metric is very big
Is there a computer algebra method to compute the curvature of a Riemannian metric on the plane when the metric tensor has long entries $E,F,G$
The computation by hand is very ...
1
vote
2
answers
327
views
Finding all submodules
Given a finite dimensional local commutative algebra over a finite field $K$ and a finite dimensional module $M$. What is the fastest/best way to obtain all submodule from $M$ using a Computer algebra ...
4
votes
0
answers
201
views
Finding Rational Curves on a Surface
Let the field of rational numbers be our base field $k$. I hope to find all rational curves on the following surface $S$ defined by $f$. You can find the motivation in the end.
$f= (x^2y^2)z^3 + (5x^...
1
vote
0
answers
109
views
generalized sieve implementations
Suppose I have a multiplicative function $f$ and I want to compute it for all integers from $1$ to $N$ (or maybe just for a long sequence of consecutive integers). It is clear that this is far faster ...
1
vote
1
answer
143
views
Omitting constraints of polynomial system
Let $n_1, n_2 \geq 1$ be known integer constants.
Suppose that we have the following system of $n$ polynomial inequalities
for which we know that there exists a feasible solution $(p_1, p_2) \in (0,1)...
10
votes
3
answers
2k
views
Web interface for GAP (or other computer algebra system dealing with finite groups)?
GAP is computer algebra system which allows to make calculations with finite groups. (See wikipedia link for an example).
Is there web interface for it ? (I cannot google it.)
Or may be some other ...
6
votes
2
answers
734
views
(Efficient) computation of symmetric powers of square matrices
I'm looking for software that can compute symmetric powers of medium-size square (say rational, 100 by 100) matrices, and ideally can do so efficiently if the matrix is sparse enough. I haven't found ...
8
votes
1
answer
751
views
How to compute with the Stark conjectures?
I would like a convenient basis for the elements of a fixed abelian extension $E$ of a real quadratic field $\mathbb{Q}(\sqrt{d})$. The accepted answer to this MO question suggests that the Stark ...
6
votes
1
answer
254
views
Algebraization of Bayesian networks?
The algebraization of classical propositional logic is Boolean algebra.
Bayesian networks are a generalization of classical propositional logic with probability truth-values.
What is the ...
6
votes
1
answer
328
views
Check irreducibility of an explicit polynomial, without computer
I have a polynomial of degree 8 in 6 variables given explicitly by
$$ (\sqrt{1+(x_1+x_2+x_3)^2+(y_1+y_2+y_3)^2}+\sqrt{1+x_1^2+y_1^2}+\sqrt{1+x_2^2+y_2^2}+\sqrt{1+x_3^2+y_3^2})\times\text{the other ...
8
votes
1
answer
215
views
Is there a good computer program for searching for endomorphisms between finite algebras which make diagrams commute? Is this problem NP-complete?
Let $(X,*),(Y,*),(Z,*)$ be finite algebras. The binary operations $*$ are not required to satisfy any identities though I am interested in the special case where $*$ is associative. Suppose that $f:X\...
5
votes
1
answer
266
views
speeding up Gosper and WZ algorithms
In our ongoing work to speed up symbolic summation and other similar algorithms in Sagemath, we notice that naive implementations of Gosper and Wilf-Zeilberger (a.k.a. WZ) algorithms are usually quite ...
1
vote
0
answers
174
views
Coefficient perturbations of polynomials with real roots only
Let
\begin{align}
P(x) &= x^n+a_{n-1} x^{n-1} +\ldots+a_0 = \prod_{i=1}^n (x-p_i)\\
Q(x) &= x^n + b_{n-1} x^{n-1} + \ldots +b_0 = \prod_{i=1}^n (x-q_i)\\
p_i, q_i& \in \mathbb{R},\ 0<...
24
votes
1
answer
682
views
two's and three's survive in gcd of Lagrange
Lagrange's four square_theorem states that every positive integer $N$ can be written as a sum of four squares of integers. At present, let's focus only on positive integer summands; that is, $N=a_1^2+...
6
votes
1
answer
248
views
Problem on triangles
Let $T\subset \mathbb{R}^2$ be any triangle and $T^t$ a deformation of $T$. Call $l_1,l_2,l_3$ the squares of the lengths of the sides of $T$ and $l_1^t,l_2^t,l_3^t$ the squares of the lengths of the ...
8
votes
1
answer
218
views
Algebraic Shifting Computer Code
Is anyone aware of computer code that will algebraically shift a simplicial complex (as in this Kalai paper)? Ideally, I am looking for an implementation that can run in something like Sage or ...
26
votes
0
answers
884
views
Where to submit this work with several unusual features?
I appreciate that questions about where to submit are generally considered off-topic, but I hope that the unusual features of the present case may make it acceptable.
I have put a monograph on github ...
1
vote
0
answers
151
views
Efficient deterministic algorithms of factorizing
My question is about efficient deterministic algorithms of factorizing polynomials of degree $n$ over $\mathbb{F}_q$.
Are there such algorithms that use poly$(n, \log q)$ bit operations?
I know ...
13
votes
1
answer
1k
views
An efficient isomorphism between finite fields
Let $p$ be a prime number. Let $f$ and $g$ be irreducible polynomials over $\mathbb{F}_p$, both of degree $n$. We know that factor-rings $\mathbb{F}_p[x]/(f)$ and $\mathbb{F}_p[x]/(g)$ are isomorphic ...
7
votes
1
answer
222
views
Computing homology of subvarieties of Euclidean spaces by persistent homology
Let $M$ be a submanifold of the Euclidean space $\mathbb{R}^n$. Let $G$ be a finite group acting on $M$ freely. I want to compute the homology (or even the cohomology ring) of $M/G$.
Suppose the ...
12
votes
1
answer
670
views
Verify that a group is hyperbolic via computer algebra
I would like to know whether there is some computer algebra software that can be used to verify if a group, given by a finite presentation, is hyperbolic (in the sense that it terminates with "yes" if ...
5
votes
1
answer
294
views
Groebner bases for differential operators with field coefficients (reference request)
Let $K$ be a field, $\partial_i$ be commuting derivations on $K$, and consider the ring $R=K[\partial_1\ldots \partial_n]$ (it is implicitly assumed that the derivations do not commute with elements ...
7
votes
1
answer
286
views
A centralised website for computational attempts in graph theory and metric geometry?
The set of questions below stems from this question.
1) does a website exist that contains (at least links to) code and data files, with the aim to centralise computational results in graph theory ...
5
votes
0
answers
191
views
Computations in Weyl algebra with rational function coefficients
I am looking for a software to perform calculations with modules over the algebra $R_n=\mathbb{C}(x_1\ldots x_n)\langle \partial_1\ldots\partial_n\rangle$ of differential operators with rational ...
10
votes
2
answers
810
views
Computing in quantum groups
I'd be interested in doing some computations in quantum groups $ U_q(\mathfrak g)$ that are conceptually simple (``is this element 0"?, and $\mathfrak g = sl_5$), but are somewhat lengthy to do by ...
1
vote
1
answer
753
views
magma generators for unit group/ sage totally positive
Does anyone know how to find explicit generators for the unit group of a number field on magma?
For example, in sage one could do
K. = NumberField(x^3+x^2-2*x-1)
UnitGroup(K).gens()
and it ...
2
votes
2
answers
363
views
Computer algebra system that test zero divisors in a quotient algebra
I have an algebra $A$ over a Noetherian ring and an ideal $I=(x,y)$, where $x,y \in A$. I need to examine whether a polynomial $h \in A$ is a zero divisor in $A/I$ or not.
Is there a computer algebra ...