The algorithms tag has no wiki summary.
1
vote
0answers
81 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
0answers
130 views
Question on a concrete example of n points [closed]
Can anyone give a concrete example of n points in the unit square (for instance, n runs from 3 through a large number) that can be generated by the algorithm here or any other algorithm or any ...
1
vote
1answer
90 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
3answers
536 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 ...
0
votes
0answers
23 views
Generate normally distributed pseudorandom numbers stating with some point [closed]
Is there any way to write recurrent formula which will provide normally distributed random numbers starting with some root, for example 123.123?
0
votes
0answers
29 views
Robust Orthogonal Match Pursuit
In a previous question I asked how to find the most compact representation of a vector as a linear combination of a set of vectors B. B has more elements (on purpose) that is needs to have to describe ...
2
votes
2answers
130 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
0answers
22 views
Reference on the wall follower maze solving algorithm [migrated]
Is there a good reference on maze solving algorithms, especially the «Wall follower» algorithm.
1
vote
0answers
25 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
3answers
96 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
1answer
81 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 ...
1
vote
1answer
99 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
2answers
113 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
0answers
114 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
2answers
46 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. ...
3
votes
1answer
64 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.
...
3
votes
2answers
165 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
0answers
19 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 ...
25
votes
3answers
986 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
2answers
87 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
1answer
54 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 ...
8
votes
2answers
120 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
0answers
59 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
1answer
95 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
1answer
250 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
0answers
106 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
1answer
64 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
1answer
99 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 ...
5
votes
3answers
329 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
1answer
119 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
1answer
156 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 ...
4
votes
1answer
348 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
2answers
133 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'), ...
8
votes
4answers
334 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
1answer
193 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 ...
3
votes
1answer
189 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
1answer
176 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 ...
0
votes
0answers
30 views
Statistics applied in A/B Testing and calculating ideal test duration for statistical significance
I'm trying to get my head around the maths used here:
http://visualwebsiteoptimizer.com/ab-split-test-duration/
Can someone point me in the right direction in terms of what algorithms/mathematics ...
8
votes
2answers
162 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
1answer
87 views
What is the Bahadur-Anderson Algorithm?
What is the Bahadur-Anderson Algorithm, and which book could one read to learn it?
1
vote
2answers
171 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
3answers
172 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 ...
4
votes
1answer
643 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
0answers
176 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 ...
18
votes
1answer
158 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
0answers
103 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
3answers
251 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
1answer
286 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
1answer
143 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
3answers
226 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 ...
