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

11
votes
0answers
115 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 ...
8
votes
0answers
73 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
74 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
173 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 $\{ ...
4
votes
0answers
65 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
526 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 ...
3
votes
0answers
36 views

Tool for construction of graph with specified properties

Is there a tool (class of algorithms for graph generation) that can construct graph with specified properties. E.g. construct graph who is homeomorphic with both to K5 and K3,3. Construct planar graph ...
3
votes
0answers
53 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
25 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
294 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
78 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
59 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
54 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
352 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 ...
3
votes
0answers
71 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 ...
2
votes
0answers
21 views

Fast Way to Compute DFT with index summation subject to a constraint

I really appreciate if anyone can help me with this problem. Problem: Let $W_n=e^{\frac{2\pi i}{N}}$ which is the $N$th root of unity. The backward Discrete Fourier Transform of a complex vector ...
2
votes
0answers
74 views

Counting problem of combinations of symmetric matrix.

Given, a symmetric $n*n$ matrix $G$ with 0,1 entries. Each row of has same number of 1. $G$ is arranged in a certain order using a rule. The rule is described below- $G$ is partitioned in to two sub ...
2
votes
0answers
27 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
44 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
39 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
372 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 ...
2
votes
0answers
51 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
58 views

The Command “TzGoGo” in GAP

I am learning GAP and would like to ask one question about a command called "TzGoGo": If $P$ is a finite presentation of a group $G$, then will the eventual result of the command "TzGoGo(P)" be ...
2
votes
0answers
136 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
512 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
105 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
35 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 ...
2
votes
0answers
305 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
436 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
424 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
16 views

Is there a way to delineate the parameter of highest influence in a system of differential equations?

So I have a system of nonlinear ordinary differential equations dependent on parameters. These equations can traditionally be solved numerically with robust methods and the solution is well defined. ...
1
vote
0answers
33 views

Simplifying the Generalized Eigenvalue Problem

Let $\Sigma_1$, $\Sigma_2$ be symmetric positive-definite real $n\times n$ matrices. We want to solve the generalized eigenvalue problem $$ \Sigma_1V=\Lambda\Sigma_2V, $$ where $\Lambda$ is the ...
1
vote
0answers
16 views

periodic boundary conditions and the FEM

I am trying to set up the mass matrix for a 1D system which I want to solve using finite elements. So the mass matrix is defined as $$ M = \int{NN^T}dL, $$ where $N$ is the finite element linear ...
1
vote
0answers
17 views

Calculate pairwise cosine distance only returning the lower triangular matrix

I have a matrix, where each row is a feature vector. I would like to find out the pairwise cosine distance between all of these feature vectors. The cosine value between all rows in a matrix could be ...
1
vote
0answers
33 views

Cholesky decomposition and rotation matrix inverse

I implemented three methods for inversion of a matrix, all are classic. I wanted to test for the most generalized method, while taking efficiency into account. For Cholesky decomposition, which is ...
1
vote
0answers
21 views

Why steepest descent gives a wrong direction search?

I have to minimize the function $ƒ(x_1,x_2)=(x_1-1)^2+x_2^3-x_1x_2$. The initial point is $[1,1]^T$. The gradient of this function is $∇ƒ(x_1,x_2)=[2(x_1-1)-x_2,3x_2^2-x1]$. This gradient evaluated ...
1
vote
0answers
56 views

What are the next few “tetranacci-like” pseudoprimes?

Starting with $n=0$: $k=2$ Given the roots $x_i$ of $x^2-x-1=0$. Then, we have the Lucas numbers, $$A_n = x_1^n+x_2^n = 2, 1, 3, 4, 7, 11, 18,\dots$$ The $n$ that divides $A_n-1$ are all the ...
1
vote
0answers
23 views

numerically solving linear integral equations

I want to solve a 3*3 linear equation system but the equations are integral equations and he coefficients of solutions are to be extracted NUMERICALLY from some other integrals.I do not know how. I ...
1
vote
0answers
23 views

Simpson's rule is not good enough for the best approximation in L2 problem

The problem came from my computation methods (practice) class. It was to write a program which does the following: Original problem statement: We have a [0; 1] segment. Let us divide it into $2^n$ ...
1
vote
0answers
24 views

Determining an unknown Function

I have an interesting operational situation at hand. I have a dependent variable, let's call it variable Y and a set of independent variables: V, H, N. (relationship is based on my operational ...
1
vote
0answers
22 views

Find largest regions bounded by a set of planes

Suppose we are given a set of planes that partition the unit cube into a large number of regions. Is there a computationally efficient way to find the region with the largest volume?
1
vote
0answers
28 views

Is there some database or software to look for patterns in polynomials?

Like if I am looking at these polynomials, $$x^8-8x^6+20x^4-16x^2+3$$ $$x^{10}-12x^8+48x^6-72x^4+33x^2$$ $$x^{12}-16x^{10}+88x^8-192x^6+138x^4$$ And I want to know if they are members of some ...
1
vote
0answers
19 views

after hajek, can we guarantee that annealing has reached a solution in the best 1%?

hajek showed in http://web.mit.edu/6.435/www/Hajek88.pdf that there are conditions under which an annealing process is guaranteed to find the global minimum. these constraints are pretty tight, but ...
1
vote
0answers
54 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 ...
1
vote
0answers
54 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 ...
1
vote
0answers
143 views

Help with proving a language is regular (Sipser problem 1.49a)

I am working through Sipser's Introduction to the theory of computation on my own, so I don't have access to a teacher. Hopefully you can help me! Giving hints is highly appreciated. This question is ...
1
vote
0answers
91 views

Solution of equations involving determinant and matrix inverse

$x$ and $y$ are two scalar unknowns. The two equations are $$|\mathbf{I}+x\mathbf{h}_1\mathbf{h}'_1+y\mathbf{h}_2\mathbf{h}'_2|=R$$ and ...
1
vote
0answers
65 views

Is there any direct method for Lagrange multiplier based domain decomposed problem?

In elastic problem, we often solve K * u = f, where K is the stiffness matrix, f the external force vector and u the displacement vector. I'm trying decompose the mesh to domains, using Lagrange ...
1
vote
0answers
41 views

How to estimate the local error and the global error for Runge-Kutta method

How to estimate the local error and the global error for Runge-Kutta method in practice? I have no idea. I recieved a nice answer on the question at other site
1
vote
0answers
17 views

Metaprogram and Metametaprogram with BLOOP

I'm solving one question and have a problem. Problem is this: Imagine $f(x)$ in the following way. We give an input $x$ to a BLOOP program $Π$ , which prints out another BLOOP program $Π_x$. Then ...