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.

Filter by
Sorted by
Tagged with
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 $\...
Pjotr5's user avatar
  • 113
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 ...
Brent Baccala's user avatar
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 ...
Boaz Tsaban's user avatar
  • 3,102
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 ...
John Palmieri's user avatar
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 ...
Christopher King's user avatar
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 ...
Christian Chapman's user avatar
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 ...
Manuel Eberl's user avatar
  • 1,181
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 ...
Mare's user avatar
  • 25.8k
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: \...
maroxe's user avatar
  • 225
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 ...
352506's user avatar
  • 991
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(...
Turbo's user avatar
  • 13.7k
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}$ ...
Problemsolving's user avatar
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 ...
IV_'s user avatar
  • 1,063
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 ...
Hauke Reddmann's user avatar
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 ...
Nikhil's user avatar
  • 263
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(\...
pavpanchekha's user avatar
  • 1,461
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 ...
Colin McLarty's user avatar
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 ...
Calvin McPhail-Snyder's user avatar
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 ...
W. Cadegan-Schlieper's user avatar
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 "...
Anton's user avatar
  • 1,573
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 ...
Peter Heinig's user avatar
  • 6,001
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 $[...
Eduardo R. Duarte's user avatar
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 ...
George Cherevichenko's user avatar
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 ...
Ali Taghavi's user avatar
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 ...
Mare's user avatar
  • 25.8k
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^...
Jiarui Fei's user avatar
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 ...
Igor Rivin's user avatar
  • 95.5k
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)...
vkonton's user avatar
  • 175
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 ...
Alexander Chervov's user avatar
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 ...
Plethy's user avatar
  • 61
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 ...
Dustin G. Mixon's user avatar
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 ...
YKY's user avatar
  • 508
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 ...
Fan Zheng's user avatar
  • 5,119
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\...
Joseph Van Name's user avatar
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 ...
Dima Pasechnik's user avatar
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<...
vkonton's user avatar
  • 175
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+...
T. Amdeberhan's user avatar
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 ...
user avatar
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 ...
Bennet Goeckner's user avatar
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 ...
Neil Strickland's user avatar
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 ...
Alexey Milovanov's user avatar
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 ...
Alexey Milovanov's user avatar
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 ...
Shi Q.'s user avatar
  • 543
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 ...
Timm von Puttkamer's user avatar
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 ...
Peter Kravchuk's user avatar
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 ...
Archie's user avatar
  • 883
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 ...
Peter Kravchuk's user avatar
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 ...
Peter Samuelson's user avatar
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 ...
Christine McMeekin's user avatar
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 ...
user279941's user avatar

1 2 3
4
5
8