Questions tagged [algorithms]
Mathematical questions about Algorithms, including the analysis of algorithms, combinatorial algorithms, proofs of correctness, invariants, and semantic analyses. See also (computational-mathematics) and (computational-complexity).
11,763 questions
-2
votes
0
answers
42
views
Does there exist any efficient polynomial time algorithm for The Cayley Embedding? [closed]
If we are given a group $G$ of order $n$, then Cayley's theorem tells us that there exists a subgroup of $S_n$ which is isomorphic to $G$. Does there exist an efficient polynomial time algorithm that ...
0
votes
1
answer
45
views
Non-negativity and/or non-positivity constraints
In a Linear Program, introducing non-negativity and/or non-positivity constraints into the Primal turns equality constraints into "regular inequality constraints" (a.k.a., inequality ...
- 2,162
0
votes
0
answers
81
views
Minimum steps to cut a truss
Motivation
While I was looking at the method of sections to find the forces in the members of a truss in engineering mechanics, I had a question about the minimum amount of calculation required to ...
- 113
0
votes
0
answers
18
views
Kim & Kim's extension to Greiner-Hormann algorithm
I am currently implementing Kim & Kim's extension of the Greiner-Hormann algorithm seen here. However i have came across an issue that i am unaware if i'm missing something or not.
I have 2 ...
- 1
2
votes
2
answers
52
views
Relationship between binary exponentiation and Horner's method evaluation of Robinson polynomials at $x=2$
Binary exponentiation provides an algorithm for calculating a power $a^n$, where you iterate over the binary digits of $a$, and at each step update
$\mathbb{val} \leftarrow \mathbb{val} ^ 2$
$\mathbb{...
- 775
1
vote
0
answers
71
views
What is the algorithm for a square root in balanced ternary?
I'm confused by wikipedia's explanation of balanced ternary's algorithm for the square root. They only show a formula I don't know how to generalize to more digits than 2, and the example given doesn'...
2
votes
1
answer
60
views
Efficiently finding out which vectors from some set are linearly independent of the other vectors in the set
I have a set $S = \{v_1, v_2, \cdots, v_N\}$ with $N$ vectors, each of which have $d$ dimensions. I would now like to find a set $S' = \{n | v_n \in \mathrm{span(}S \setminus \{v_n \}) \}$, i.e. the ...
- 45
0
votes
0
answers
212
views
Efficient algorithm for solving Diophantine equation $x ^ 2+y ^ 3+z ^ 5=w ^ 7$ with $\gcd (x, y, z)=1$.
My Mathematica Codes:
...
- 305
5
votes
2
answers
285
views
Is there any algorithm which can find a common divisor of two polynomials modulo $p^k$?
Let us consider two monic polynomials $f(X), g(X) \in \dfrac{\mathbb{Z}}{p^k\mathbb{Z}}[X]$. Now, we call $h(X)$ is a divisor of $f(X)$, if there exists a $l(X) \in \dfrac{\mathbb{Z}}{p^k\mathbb{Z}}[X]...
- 3,919
-1
votes
1
answer
91
views
Gaussian elimination modulo $4$ [closed]
Does anyone know how to perform Gaussian elimination modulo $4$? Are there any ready-to-use code snippets or relevant websites available? I find that there are almost no existing code implementations ...
- 1
3
votes
1
answer
100
views
Is there a simple algorithm for approximating an imperfect offset polyline?
I've got a polyline of straight line segments to which I'd like to calculate an offset polyline (like an offset curve, but described as a sequence of connected non-arcing line segments). This is ...
- 131
5
votes
0
answers
48
views
Are there Salem-Spencer sets with bounded absolute second forward difference?
A Salem-Spencer set is a set of numbers no three of which form an arithmetic progression.
Suppose $A$ is a Salem-Spencer set. And let $(a_n)_{n=1}^{\infty}$ be the set $A$ written as a strictly ...
- 25k
3
votes
2
answers
102
views
Can LP calculate maximum/minimum eigenvalue of a matrix
It's not hard to show that the maximum eigenvalue of a matrix $A\in \mathbb{S}^n$ can be calculated through the following SDP:
\begin{align*}
\max&\ Tr(AX) \\
\text{subject to}& \ Tr(X) = 1\\
...
- 93
1
vote
0
answers
34
views
Unorthodox implementation for a recursive identification method
Recently I realized that I've coded a custom-made function for recursive output error method which differs a bit from the traditional algorithm and would like to know the perception of my peers. ...
- 141
1
vote
0
answers
42
views
Introducing affine equality constraints into convex programs
In this lecture (43:39 - 44:10) and this lecture (1:11:13 - 1:12:46), Stephen Boyd hints at a method for introducing equality constraints into a convex program. The notation from the lectures is
$$\...
- 2,162