This tag concerns computational problems central to mathematical and scientific computating. The scope includes algorithms, numerical analysis, optimization, and linear algebra, computational topology, computational geometry, symbolic methods, and inverse problems.

learn more… | top users | synonyms

31
votes
0answers
514 views

On Ramanujan's curious equality for $\sqrt{2\,(1-3^{-2})(1-7^{-2})(1-11^{-2})\cdots} $

In Ramanujan's Notebooks, Vol IV, p.20, there is the rather curious, $$\sqrt{2\,\Big(1-\frac{1}{3^2}\Big) \Big(1-\frac{1}{7^2}\Big)\Big(1-\frac{1}{11^2}\Big)\Big(1-\frac{1}{19^2}\Big)} = \Big(1+\frac{...
14
votes
0answers
168 views

Product of primes mod n

Let $n$ be an odd composite number. I'm trying to compute $$ f(n)=\prod_{n/2<p<n}p\pmod n $$ where $p$ ranges over the primes in the indicated region. Can this be done (significantly) faster ...
9
votes
0answers
108 views

Generalizing Bellard's “exotic” formula for $\pi$ to $m=11$

Bellard's "exotic" pi formula has the form, $$a\pi+b = \sum_{n=1}^\infty \dfrac{P(n)}{{\displaystyle \binom{mn}{2n}2^{n-1}}}$$ where $a,b,m$ are integers and he uses $m=7$. However, it seems there ...
5
votes
0answers
87 views

On a unique(?) binomial property of $3003$

Given the triangular number, $$T_k = \frac{k(k+1)}{2}$$ and remembering that, $$\binom{n}{m}=\binom{n}{n-m}$$ Excluding $a_0=1$, we then have the six-fold (at least) equalities, $$\begin{aligned} ...
5
votes
0answers
132 views

A summation involving the ceiling function

I'm trying to find a better method of calculating the sum $$\sum_{k=1}^N\lceil ak\rceil^2$$ where $a$ is an irrational number. So far, my only idea is to somehow use a best rational approximation. ...
5
votes
0answers
185 views

A property of the subgroups lattices

Let $G$ be a finite group. Consider all the subgroups $H$ such that its subgroups lattice $\mathcal{L}(H)$ is distributive (i.e. the group $H$ is cyclic, by Ore's theorem), and among them, let $\{ H_{...
4
votes
0answers
116 views

How to keep up when converting between bases?

Here is a schematized binary channel that neatly conveys a decimal number. $ \require{begingroup}\begingroup \def\T {{ \cal T }} \def \Ti {{ \T \raise5mu{ \text- \scriptsize 1 } }} \def\Bx #1{{ ~ ...
4
votes
0answers
537 views

Two-layer Perceptron for XOR

I'm reading Neural Networks for Pattern Recognition by Christopher M. Bishop. It's for a physics class, but I think the problem is closer to mathematics so I'm asking here instead of PSE. Chapter 4 of ...
4
votes
0answers
70 views

Finding every $n$ such that $n\times$ ('reverse' number of $n)=m^2$ such as $1584\times 4851={2772}^2$

Let $r(n)$ be the 'reverse' number of $n$ in the decimal system. For example, $r(1234)=4321$. Then, here is my question. Question : Can we find every $n(\in\mathbb N)$, which is not a square ...
4
votes
0answers
540 views

Obtain a contradiction

Motivation : The motivation is to show that the equation $x^{2b}.x^{2a} +(3-x^{2b}) x^{a} + (1-s^2)=0 $ has no solutions in integers for any values of $x,b,a,s$ ( choosen as per the constraints ...
4
votes
0answers
85 views

is there a computationally efficient formula for computing the mutual information between two continuous variables?

I need to compute the mutual information between two continuous variables. Below is an equation shown to compute the mutual information between a variable $X$ and $Y$. $I(X;Y) = \int_Y \int_X ...
3
votes
0answers
52 views

Why using primes as base in the Rabin-Miller test?

I have done some computer tests with the Rabin-Miller primality test: To test an odd number $n$, write $n=2^r\cdot s + 1$, where $s$ is odd. Given a number $a$ such that $1<a<n-1$, if $...
3
votes
0answers
56 views

Is there a systematic way of “discovering” an algebra from observations of its universe?

I am faced with the following situation: I have a finite set of some $m$ positive integers $Q^m \in \mathbb{N}$ These integers go through a series of $N$ possible black boxes that transform them. ...
3
votes
0answers
118 views

Computing the density of a set of multiples

I have a finite* set $A=a_1<\cdots<a_r$ of positive integers. Define $B$ as the set of positive integer multiples of $A$ and $$ A_1=\frac{1}{a_1} $$ $$ A_k=\frac{1}{a_k}-\sum_{i<j<k}\frac{...
3
votes
0answers
73 views

A Free Boundary Problem

Is there any special way to solve such a problem. Any idea would be appreciated. At least does anybody know which method is useful to solve this problem numerically? Is it even solvable numerically? ...
3
votes
0answers
26 views

Has there been work on computational group theory applications to computing colimits of crosses n-cubes of groups?

I'm trying to compute homotopy groups of a few spaces using crossed n-cubes of groups. I'm able to describe a few colimits in terms of quotients of induced crossed modules and nonabelian tensor ...
3
votes
0answers
514 views

Nerve Theorem: Is the finite union of closed convex sets triangulable?

My Question: Let $A_1, \ldots, A_k \subseteq \mathbb{R}^n$ be closed convex sets. Is the union $\bigcup_{i=1}^k A_i$ triangulable$^1$? If so, why? Background: I'm trying to better understand the ...
3
votes
0answers
84 views

Computing the decomposition of a representation of $S_n$

I have an explicitly defined representation of the symmetric group that I would like to decompose into irreducibles. How to do this most easily? The best approach I have so far is as follows: Find a ...
3
votes
0answers
70 views

Algorithm for primary decomposition of ideals in a power series ring over a field

Let $K$ be a field such that there exists an algorithm for factoring a polynomial over $K$ into the product of irreducible polynomials. For example, the field of rational numbers $\mathbb{Q}$ is such ...
3
votes
0answers
64 views

Supremum over unitary group action

Let $A$ and $B$ are two given Hermitian operators on matrix algebra $M_n(\mathbb{C})$. $A$ is positive semi-definite with unit trace. I want to know the general method for calculating the following ...
3
votes
0answers
440 views

“Green Globs” question

When I was in high school geometry, we had a fun little game on the computer called Green Globs (the website for the software is http://www.greenglobs.net/index.html). A number of targets (globs) are ...
2
votes
0answers
29 views

Egyptian fraction with least possible sum

Suppose that $~a~$ and $~b~$ are coprime positive integers. Then there exists representation of $~\frac{a}{b}~$ as egyptian fraction: $$~\frac{a}{b} = \frac{1}{d_1} + \cdots + \frac{1}{d_s} ~$$ There ...
2
votes
0answers
19 views

Method to Linearise PDE

I have a Monge-Ampere-type PDE I wish to solve using a finite difference method: $$(1-u_{xx})(1-u_{yy}) -u_{xy}^2 = f(x,y).$$ Is there generally a preferred method for linearising the system after ...
2
votes
0answers
34 views

Algorithm for numerically calculating $\log x$

It was while fiddling yesterday that I came up with this rather pretty approximation: $$\log x = \frac{1}{2\epsilon}(x^{\epsilon}-x^{-\epsilon})+\mathcal{O}(\epsilon^2)$$ To be more precise, $$\...
2
votes
0answers
38 views

How to find values of x where $a_i x$ are nearly integers? $a_i \in \Bbb R$

I have a set $\{a_i \in \Bbb R | \ i <=7 \}$, and I'm looking for a way to find values of $x$ where given $\epsilon > 0$, $$\forall i \ \exists n_i \in \Bbb{Z} \ \ |a_i x - n_i| < \epsilon$$ ...
2
votes
0answers
18 views

Given a set of integers $S$, what is the maximum integer that is a product of one or more integers from $S$ not exceeding $X$?

Given a set of integers $S$, which will contain no more than $100$ integers. Now, what would be the fastest approach to find $M$ which is a product of one or more integers from $S$ (and multiple usage ...
2
votes
0answers
50 views

A recursive problem with GAP concerning lists and an iterator loop

I have the following question concerning a list algorithm in GAP: Let $L_1$ be a non-empty list with certain objects as entries. I wrote a program and called it helping_program_1. The Input for ...
2
votes
0answers
34 views

terms of taylor expansions of multiple variables at the origin

By the fundamental theorem of symmetric polynomials, $X_1,X_2,\cdots,X_n$ are polynomials of $ e_1,\cdots,e_n$ and $$ \mathbb{Z}[ e_1,\cdots,e_n]=\mathbb{Z}[X_1,X_2,\cdots,X_n]. $$ We define a ...
2
votes
0answers
54 views

Summation of n terms of a series$ 1+2+8+64+…$

In one of my problem , I got a series as $1$,$2$,$8$,$64$,$1024$...and so on. can we really get a sum expression for that series$???$ If yes, then what is the expression $f$ $?$ or the sum of $n$ ...
2
votes
0answers
75 views

I have a finite permutation group and access to a computer algebra system, how can I recognize the structure of the group?

I have a fixed permutation group $G$, and cannot tell which finite group it really is in a "human readable" way. I also have GAP. Is there a step by step computation to give me the structure of this ...
2
votes
0answers
21 views

How to compute Generalized Group Inverse?

Given a transition matrix $P \in \mathbb{R}^{n \times n}$, i.e. $\sum_j P_{ij} = 1$ and $P_{ij} \geq 0$ for all $i,j$. One can show that there exists a unique group inverse $B$ of $A:= I - P$ which ...
2
votes
0answers
36 views

Good method for finding roots that *usually* fall within an interval?

I've been using Brent's method to find the roots of a monotonic, nonlinear, non-differentiable function. The roots often fall within a known interval, but Brent's method fails if they occasionally ...
2
votes
0answers
80 views

An elliptic curve for the multigrade $\sum^8 a_n^k = \sum^8 b_n^k$ for $k=1,2,3,4,5,9$?

I. The first solution to, $$\sum^6_{n=1} a_n^9 =\sum^6_{n=1} b_n^9$$ $$13^9+18^9+23^9-5^9-10^9-15^9 = 9^9+21^9+22^9-1^9-13^9-14^9$$ was found in 1967 by computer search by Lander et al. It stood ...
2
votes
0answers
81 views

Is there any efficient progam or software to calculate the fractional chromatic number?

The fractional chromatic number $\chi_f(G)$ is a generation of the chromatic number of a graph $G$. It can be formulated as a linear programming question: Let $\mathcal{I}(G)$ be the set of all ...
2
votes
0answers
50 views

Computer program to simplify formulas

What is the computer program that attempts to simplify sums of binomial coefficients, factorials, etc.? Possibly Zeilberger wrote it, but I'm unsure. If so, possibly it was talked about in his A=B ...
2
votes
0answers
40 views

Quantitatively comparing event trains of different lengths for Poissonness

I have a parameterized, effectively black box process that generates a series of events (simulated action potentials). Different parameter values often lead to different numbers of events. How can I ...
2
votes
0answers
58 views

LLL and factoring polynomials in $\Bbb Z[x]$

Given a degree $2k$ reducible polynomial $f(x)=\sum_{i=0}^{2k}a_ix^i\in\Bbb Z[x]$ with $gcd(a_{2k},\dots,a_0)=1$ that is known to be of the form $f_1(x)f_2(x)$ with $deg(f_i(x))=\frac{deg(f(x)}{2}=k$ ...
2
votes
0answers
205 views

Using GAP to compute the abelianization of a subgroup

Let $K$ be the group generated by four elements $x_1,\cdots,x_4$ with relations that each generator commutes with all its conjugates. (An equivalent relation is, any simple commutator with repeated ...
2
votes
0answers
707 views

Solving large, sparse system of linear equations

I have a system of linear equations as follows: $$(A+I)x=B$$ where $I$ is the $n\times n$ identity matrix, $A$ is a $n\times n$ matrix such that the first and last rows are blank, and, for every ...
2
votes
0answers
131 views

Solving a particular system of Diophantine equations in $n$ variables (Frobenius equations)

I have a particular system of linear Diophantine equations in $n$ variables for which I need to find all nonnegative integer solutions. Specifically, they are Frobenius equations, meaning the ...
2
votes
0answers
37 views

Computing a particular finite set of quaternion matrices.

Let $B = \left(\frac{-1,-11}{\mathbb{Q}}\right)$ be a choice of quaternion algebra ramifying at $11$ and consider the maximal order $\mathfrak{O}=\mathbb{Z}\oplus\mathbb{Z}i\oplus\mathbb{Z}\frac{1+j}{...
2
votes
0answers
399 views

How to convert a hologram into an image?

Suppose one knows in full detail the phase and intensity of monochromatic light in a plane. This is basically what a hologram records, at least for some section of a plane. By using this as the ...
2
votes
0answers
533 views

Logistic regression algorithm in Casio and Texas Instruments calculators

When using logistic regression on a Casio or Texas Instruments calculator, the output is of the form $$f(x) = \frac{c}{1+ae^{-bx}} $$ The problem I have (when teaching in a class where both types of ...
2
votes
0answers
488 views

Clarification on different types of solutions: analytical, closed form, iterative, algorithmic,

When doing computation, there are different types of solutions: analytical, closed form, iterative, algorithmic, exact, approximate, ... (there are probably more than I just listed and please don't ...
1
vote
0answers
32 views

R $\subseteq \omega$ recursive iff $\exists m \in \omega$ such that $R=\{n \ | \ \bar{\omega} \models \phi[m,n] \}$.

The queston I'm trying to solve is use Kleene's enumeration theorem to show R $\subseteq \omega$ recursive iff $\exists m$ such that $R=\{n \ | \ \bar{\omega} \models \phi[m,n] \}$ for some $m \in \...
1
vote
0answers
38 views

Normalizing an elliptic curve to find integer solutions

I have an elliptic curve $$ c_1y^2 + a_1xy + a_3 = c_2x^3 + a_2x^2 + a_4x + a_6 $$ with integers $a_1,a_2,a_3,a_4,a_6,c_1,c_2$ and I would like to find all integer solutions of this elliptic curve. I ...
1
vote
0answers
25 views

Ordering of elements in the base of a group

In section 4.6.7 of HANDBOOK OF COMPUTATIONAL GROUP THEORY, the authors use an ordering $\prec$ for the elements in a coset. That ordering, $\prec$, was defined in section 4.6 as follows. Throughout ...
1
vote
0answers
16 views

Good numerical method for finding the eigenvalues and eigenfunctions of the Dirichlet-Laplacian?

Let us confine ourselves to 2D. What is the best numerical method for solving the eigenvalues and eigenfunctions of the Dirichlet-Laplacian operator? Possibly, it depends on the shape of the domain? ...
1
vote
0answers
30 views

How to use CVXOPT to solve an semidefinite programming problem

I'm using Sage to solve a problem and would like to use cvxopt to solve a sdp problem. Specifically, I have a list of expressions of the form $$c + \sum_{i,j} a_{i,j} q_{i,j}$$ where each $c$ and all ...
1
vote
0answers
53 views

Looking for a perfect square

I have a base number and I add to this number in increments. Is it possible to calculate where is the nearest perfect square without going through all the numbers? Example: Base number 11 Increment ...