# Tagged Questions

**3**

votes

**1**answer

46 views

### Random weighted selection without replacement

I am using the following procedure to select $m$ different numbers $\{i_1,\ldots,i_m\}$ from the set $\Omega = \{1,\ldots,N\}$, with $m,N\in\mathbb{N}$ such that $m< N$.
Selection procedure
...

**2**

votes

**1**answer

179 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 ...

**7**

votes

**3**answers

631 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 ...

**4**

votes

**2**answers

211 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

25 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 ...

**2**

votes

**3**answers

135 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 ...

**6**

votes

**2**answers

178 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'), ...

**4**

votes

**1**answer

370 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 ...

**2**

votes

**1**answer

2k views

### FFT and Butterfly Diagram

Wikipedia presents butterfly as "a portion of the computation that combines the results of smaller discrete Fourier transforms (DFTs) into a larger DFT, or vice versa (breaking a larger DFT up into ...

**8**

votes

**3**answers

710 views

### Complexity of matching red and blue points in the plane.

I'm just asking because I'm curious.
I was seeking references on the following problem, that a friend exposed to me last holidays :
Problem
Given $n$ red points and $n$ blue points in the plane in ...

**11**

votes

**1**answer

485 views

### The word problem in the ring of polynomials

This question must be well known but I cannot find it in the literature.
Question: What is the computational complexity of the word problem in a subring of the ring of polynomials in $n\ge 1$ ...

**2**

votes

**0**answers

328 views

### Hamiltonian paths in subgraphs of rectangular lattice graphs

Is following decision problem NP-hard / NP-complete:
Having vertex-induced subgraph of rectangular lattice graph determine if any Hamiltonian path exists
Having vertex-induced subgraph of ...

**0**

votes

**2**answers

618 views

### Fast algorithms for computing nullspace of a positive semidefinite matrix over Z

Let $A \in \mathbb{Z}^{n \times n}$ be a positive semidefinite sparse matrix. I am looking for asymptotically fast algorithms for computing the nullspace basis of $A$ (or just random elements in the ...

**8**

votes

**1**answer

1k views

### All-pairs shortest paths in trees?

This is a reference request, since I'm sure what follows isn't new, but I can't seem to find it.
Suppose that we have a finite tree $T$ with non-negative weights on the edges. Naively, computing the ...

**3**

votes

**1**answer

197 views

### Theorems about the directed bandwidth of a rooted tree?

Let $T$ be a rooted tree with root $r$. Say an ordering $v_1,\ldots,v_n$ of the vertices of $T$ is a search order if $v_1=r$ and for all $2 \leq i \leq n$, there is $j < i$ such that $v_j$ is the ...

**15**

votes

**6**answers

3k views

### Algorithms for finding rational points on an elliptic curve?

I am looking for algorithms on how to find rational points on an elliptic curve $$y^2 = x^3 + a x + b$$ where $a$ and $b$ are integers. Any sort of ideas on how to proceed are welcome. For example, ...

**8**

votes

**0**answers

109 views

### Disjoint Rooted Paths with Specified Patterns

Let $S:=$ { $s_i : i \in [k]$ } and $T:=$ { $t_i : i \in [k]$ } be disjoint subsets of vertices of a graph $G$. Furthermore, let $A$ be a subset of $S_k$ (the symmetric group on $[k]$). A set of ...

**4**

votes

**2**answers

377 views

### Algorithms for modeling asynchronicity in Asynchronous Cellular Automata

Most cellular automata are defined as being updated synchronously. I am interested in asynchronous automata, where they do not all have to update simultaneously. I am restricting myself to cellular ...

**2**

votes

**2**answers

240 views

### Reference request: given a divisor d of N, how quickly can I obtain the largest factor of N coprime to d?

This is quite likely to be a solved problem, perhaps even a standard exercise. However, being a non-[number theorist], I don't know where to look. A quick perusal of the basic starting references ...

**1**

vote

**3**answers

326 views

### Numerical algorithms on mixed-precision computational models.

I want to learn more about numerical algorithms that use mixed-precision computational models (where instead of everything being 32/64 bit floating points, we can do lower precision calculations at ...