The algorithms tag has no wiki summary.

**1**

vote

**0**answers

92 views

### Testing functional equivalence

We are looking for the most efficient (most recent, or best) techniques to check if two algebraic expressions (elementary, Calculus-type functions) are equivalent (or if an expression is equivalent to ...

**2**

votes

**1**answer

128 views

### Complexity of numerically solving systems over the reals

Basically I am interested in
What is the complexity of numerically solving systems over $\mathbb{R}$?
By solving I mean finding at least one numeric solution with given
precision.
Probably the ...

**0**

votes

**1**answer

256 views

### Algorithm to efficiently sum N boolean numbers. [closed]

I am looking for a fast algorithm to do the following task: Given $N$ numbers $a_i, i=1,..., N$, where $a_i$ can be equal to $0$ or $1$, compute the number $s \equiv \sum_{i=1}^N a_i$ in base 2. ...

**7**

votes

**1**answer

246 views

### Main problems on lattice-basis reduction algorithms (such as LLL)?

What are the main open problems on lattice-basis reduction algorithms (such as LLL)? I am looking for problems satisfying the following two conditions:
(a) their solution would likely be of some ...

**2**

votes

**1**answer

188 views

### RefReq: Algorithms for standard operations in Algebraic Number theory

Given an algebraic number field $F$ (I actually don't have an idea how to implement this data already, except for splitting fields of polynomials, but there is something in SAGE) is there free code ...

**1**

vote

**1**answer

133 views

### Generating k-partite graphs

Does there exist an efficient algorithm for generating all non-isomorphic k-partite graphs up to a certain order $n$? I've read through the nauty tutorial, but it doesn't look like anything beyond ...

**7**

votes

**3**answers

692 views

### smooth manifolds as real algebraic set (continued)

There are several ways of producing manifolds,say:
1.orbits space of group action
2.connected sum of manifolds
3.underlying topological space of nonsingular algebraic set
....
here,i am ...

**3**

votes

**2**answers

220 views

### Geodesics in Graphs:Shortest Paths vs Going as Straight Ahead as Possible

According to Wikipedia http://en.wikipedia.org/wiki/Geodesic, a geodesic " is a generalization of the notion of a "straight line" to "curved spaces " and further " In the presence of an affine ...

**2**

votes

**0**answers

125 views

### Row subset selection of matrix to optimize condition number

Given a matrix $\mathbf{A} \in \mathbb{C}^{N\times M}$ with $N \gg M$. This matrix results from a linear equation system and has a certain structure (however, I do not think that details provide any ...

**1**

vote

**3**answers

202 views

### Simulating Mixed Nash Equilibria

I have a $N$ person game where each person has a set of $M$ discrete strategies. I know from the theory that at least one mixed strategy Nash Equilibrium exists.
Can someone please tell me how do I ...

**1**

vote

**1**answer

120 views

### Do there exist a way to solve inhomogeneous matrix equations Ax = b for only selected rows?

The inhomogeneous matrix equation $\mathbf{A} x = b$ can be solve in many ways, but in this particular case, I am looking for a solution to this problem on a set of constraints.
The matrix $A$ is ...

**2**

votes

**1**answer

383 views

### Finding integer points inside of a parallelogram

Suppose $P = \{p_1,\ldots,p_4\} \in \mathbb{R}^2$ defines a quadrilateral (here, specifically, a parallelogram). In the particular case I'm dealing with, I know that there exists at least one point ...

**4**

votes

**2**answers

198 views

### Estimate size of graph by taking random walks

Let $G$ be a connected, finite graph and let $v_0$ be a vertex of $G$. I'm interested in methods of estimating the number of vertices in $G$, based on local exploration only. What I have in mind is:
...

**4**

votes

**0**answers

167 views

### Rough structure of the double coset space/Graph bijections up to automorphisms

I am dealing with bijective maps $\pi:\Gamma_1\to \Gamma_2$ between two graphs with the same number of vertices $N=O(10)$.
The graphs have a significant automorphism group (these are disconnected ...

**3**

votes

**2**answers

462 views

### Hyperrectangle partition of set of overlapping hyperrectangles

I have a set of $n$, $d$-dimensional hyperrectangles which may be overlapping in arbitrary ways. I would like to partition the area covered by this set into a set of non-overlapping hyperrectangles. ...

**2**

votes

**1**answer

385 views

### Finding the vertices of a convex polyhedron from a set of planes

I'm new to computational geometry and advanced mathematics in general here so bear with me. I've spent a decent amount of time attempting to figure out this problem and I just can't find a solution.
...

**4**

votes

**2**answers

236 views

### Reference Request: Representing Positive Integers as Differences with Minimal Hamming Weight

Background of my reference request is an observation that I made, while I was still in school: there are two ways to calculate $x*999$: either do it directly, by applying the multiplication algorithm ...

**2**

votes

**0**answers

27 views

### In what paper was the shrinkage parameter introduced to the nelder-mead simplex direct search algorithm?

I have read lots of papers referencing a 4th shrinkage parameter when talking about the Nelder Mead Simplex method. However, I cannot see any shrinkage parameter in the flow chart of the original ...

**28**

votes

**3**answers

2k views

### Are surjectivity and injectivity of polynomial functions from $\mathbb{Q}^n$ to $\mathbb{Q}$ algorithmically decidable?

Is there an algorithm which, given a polynomial $f \in \mathbb{Q}[x_1, \dots, x_n]$,
decides whether the mapping $f: \mathbb{Q}^n \rightarrow \mathbb{Q}$ is surjective,
respectively, injective? --
And ...

**2**

votes

**3**answers

143 views

### Reference Request for: Finding Large Bipartite Subgraphs via Destruction of Odd Cycles in Graphs

From the observation, that a bipartite graph doesn't contain odd cycles, it would seem natural to attempt to destroy all odd cycles in the most efficient way, by either removing edges or vertices of ...

**3**

votes

**1**answer

286 views

### Practical error-estimates for (adaptive) Newton-Cotes Quadrature

I am looking for practical error estimates for Newton-Cotes Quadrature rules.
Most books on numerical methods I have found mainly deal with theoretical error bounds/estimates for the respective ...

**5**

votes

**2**answers

273 views

### Covering convex polygons with inscribed disks

The following problem came up when discussing mapping software (e.g., Google maps) with computer scientists. By $B(c,r)$ I mean the planar disk (open or closed, it doesn't matter) of radius $r$ around ...

**3**

votes

**0**answers

124 views

### On understanding Discrete-Valued Stochastic Processes( time series, panel data )

It seems to me that a significant proportion of work in probability theory, statistics and machine learning are on understanding continuous-valued, relatively weakly dependent, or linear dependent ...

**4**

votes

**1**answer

108 views

### Algorithm to detect if an element of a (commutative) ring is in a subring?

For rings finitely-generated over a field, the theory of Groebner bases gives us quite an efficient algorithm for determining whether an element of the ring is in a given ideal of the ring.
Is there ...

**7**

votes

**2**answers

336 views

### Quickly finding optimal subset of pairs of numerator and denominator terms for special objective functions

Given a multi-set of pairs $((a_i,b_i))_{i \in Y}$ of positive numerator and denominator terms (i.e. each pair has one numerator term and one denominator term), my general problem is to find the ...

**3**

votes

**0**answers

199 views

### Beating Kadane's Algorithm

I am seeking some reference on already existing work for the following problem.
Given an $n$-dimensional square matrix $A=DP$ where $D$ is a diagonal and $P$ is a permutation matrix (think of Gaussian ...

**1**

vote

**1**answer

87 views

### computing $c_5$ in “Primality testing with Gaussian periods”

As far as I know, the April 2011 version of #143 on this page has not been improved upon.
On page 10 of that paper, the authors give an algorithm that uses a constant $\:c_{\hspace{.01 in}5}\:$.
...

**1**

vote

**1**answer

139 views

### What algorithms do you know for beltway reconstruction?

I've faced the beltway reconstruction problem and I've developed a simple backtrack algorithm, what algorithms do you know for this problem?
Beltway Reconstruction Problem:
Assume there is a set of ...

**6**

votes

**3**answers

733 views

### Square Root Algorithm

I would like an efficient algorithm for square root of a positive integer. Is there a reference that compares various square root algorithms?

**2**

votes

**1**answer

162 views

### Algorithm to find if an element X can be represented with the sum of one number of each subset in $O(n^2)$?

Here is the problem:
I have 3 subsets ( called $S_1$, $S_2$ and $S_3$) that each have $N$ elements (arbitrary elements).
So I have one element $X$. I want to know if I can get $X$ making the sum of ...

**2**

votes

**1**answer

202 views

### Algorithm for representing a polynomial as a composition of lower degree polynomials

Let $q$ be a large prime and $e$ an integer such that $GCD(e,q-1)=1$. Let $p(x)$ be a polynomial of degree $e^n$ with coefficients in $\mathbb Z_q$ such that there exists a progression of polynomials ...

**5**

votes

**1**answer

463 views

### Difference Sets

Suppose
$$
P \subseteq \{1,2,\dots,N\},\quad |P| = K
$$
We calculate the differences as: $$d=p_i-p_j\mod N,\quad i\ne j$$
Now let $a_d$ denote the number of occurrence of $d$ (for $d = 1, 2, \dots , N ...

**6**

votes

**2**answers

207 views

### Recovering a Weighted Graph from Shortest Path Distances

I am interested in the following problem (A) and its related formulation (B).
(A) Suppose that $G = (V,E,w)$ is an unknown weighted graph on the vertex set $V$ and that one has access to $d_G(v,v'), ...

**14**

votes

**5**answers

569 views

### Mathematics of privacy?

I wonder to which extent the current public debate on privacy issues (not only by state sniffing, but e.g. by microtargetting ads too an issue) offers interesting questions in mathematics?
Can we ...

**3**

votes

**1**answer

218 views

### Is the prime ideal principal which is in 256-th cyclotomic ring lying over 257?

As we known, the integer ring R of 256-th cyclotomic field is not a Principal Ideal Domain.
And rational prime 257 is split completely in R.
Suppose prime ideal P of R is an arbitrary ideal lying ...

**5**

votes

**1**answer

645 views

### Any reference to an algorithm for finding the largest empty circle on a sphere (with great-circle distance)?

Given a set $S$ of 2D points in the plane, there are known algorithms for finding the largest empty circle ($LEC$) of the set of points.
The $LEC$ problem is stated in this way: find a $LEC$ whose ...

**4**

votes

**1**answer

326 views

### Checking if a binary vector lies in the affine span of given binary vectors

Let $x_1,\ldots,x_N \in \{0,1\}^D$ be $N$ binary vectors in ${\mathbb R}^D$, assumed affinely independent. Is there an efficient algorithm for determining whether a new binary vector $x_{N+1}$ is in ...

**4**

votes

**1**answer

210 views

### convex polyhedron in the unit cube

Let $P$ be a given finite set of points within the $n$-dimensional unit cube. A finite set $Q$ of points within the $n$-dimensional unit cube covers $P$ if $\operatorname{conv}(Q) \supseteq P$ where ...

**8**

votes

**2**answers

220 views

### Ideal Membership without Certificate?

I have a homogeneous ideal $I=\langle f_1,\ldots,f_r\rangle$ of the polynomial ring $\mathbb C[X_1,\ldots,X_n]=:R$ where each of the $f_i$ is actually over $\mathbb Z$. My computations are usually ...

**0**

votes

**1**answer

122 views

### What is the Bahadur-Anderson Algorithm?

What is the Bahadur-Anderson Algorithm, and which book could one read to learn it?

**1**

vote

**2**answers

1k views

### Trilateration problem

When trying to develop an algorithm for a program, I got with the following problem:
Determine the approximate location of $O$, if you can take finite samples $P_n$ from known locations and always ...

**1**

vote

**3**answers

221 views

### Strategic vertex labeling

We are given a graph $G=(V,E)$ with positive edge weights $w_{i}$ and numerical {0,1,-1} labels $l$ for all vertices . We know that $G$ has a subset $G'$ with all vertices labeled 0(all vertices with ...

**5**

votes

**2**answers

794 views

### Solve for $A$ and $B$ in $AXB=Y$

Let $R = \mathbb{Z}[x_{1}, \dots, x_{r}]$.
Let $X$ be $n \times n$ matrix with entries in $R$.
Let $Y$ be $m \times m$ matrix with entries in $R$ formed from $\mathbb{Z}$-linear or $\mathbb{R}$-linear ...

**4**

votes

**0**answers

284 views

### Checking whether an element is in all inclusion-wise maximal common independent sets of two matroids

Given two matroids $M$ and $M'$ over the same universe $E$, and some element $x \in E$, I am interested in the importance of $x$ for the intersection (the common independent sets) of $M$ and $M'$.
It ...

**26**

votes

**1**answer

429 views

### Decidability of equality of expressions built using 1,+,-,*,/,^

Consider expressions built using number $1$, arithmetical operators $+, -, *, /$ and exponentiation ^ (in case of multiple values, the principal value is assumed, the same way as it implemented in ...

**7**

votes

**0**answers

141 views

### How quickly can we test if a graph is distance-regular?

A (simple, finite, connected) graph $G$ is distance regular if there exist integers $b_i,c_i,i=0,...,D$ such that for any two vertices $x,y$ in $G$ and distance $i=d(x,y)$, there are exactly $c_i$ ...

**3**

votes

**3**answers

799 views

### L-systems and Sierpinski Triangle

I was just shocked when I saw these consecutive outcomes of an L-system converging to the Sierpinski triangle (shown in the picture below).
I'm interested to know how could one arrange the rules of ...

**3**

votes

**1**answer

345 views

### Fastest Digit Extraction for Any Irrational Number

I believe the current lowest-memory algorithm for computing the $n^{th}$ binary digit of $\pi$ requires $O(log(n))$ bytes and $O(n^2 log(n))$ days (I pick Bellard over Bailey–Borwein–Plouffe for ...

**0**

votes

**1**answer

221 views

### Giving a general term of a recursive function, and upper bound for it

Let a constant $B \ge 1$, and let $l_1 = 0$, $b_1 = 0$ be the values of $l$ and $b$ (respectively) at time $t = 1$.
Let $l_{t+1} = l_t + 1$ if $b_i < B$, and $l_{t+1} = l_t$ otherwise
Let ...

**2**

votes

**3**answers

273 views

### existence of equivalence checking algorithm

Set D : Set of decision algorithms
X∈D if and only if
X is an Turing machine algorithm with finite length
takes one input i, binary number
X(i)=0 or X(i)=1 or X(i) runs ...