Questions tagged [algorithms]
A description of the specific steps needed to solve a particular problem in an unambiguous way, expressed in an abstract form.
514
questions
7
votes
2answers
2k views
Markov (Chain) image generators?
Markov Chains can be used to generate, or auto-complete, text.
https://en.wikipedia.org/wiki/Markov_chain#Markov_text_generators
Training text is read, and some information about the text is ...
2
votes
0answers
57 views
Where does the seemingly official number of certain algorithms come from?
There are a lot of algorithms which seem to have been supplied an official number, such as Algorithm 76, Hierarchical clustering using the minimum spanning tree. Another example is Algorithm 123, ...
0
votes
1answer
65 views
tea bag flavors mixing algorithm [closed]
I bought three boxes of tea bags with different flavors (A, B, C).
I wish to mix them in such a way that
- there is never two consecutive bags of the same flavor (ABCCAB is avoided) ;
- the mixing ...
4
votes
0answers
99 views
FFT-based Image Rotation Algorithms More Accurate Than Chirp-Z?
We're currently using a Chirp-Z based implementation:
R. W. Cox and R. Tong, "Two- and three-dimensional image rotation using the FFT," IEEE Trans. Image Processing, vol. 8, no. 9, pp. 1297–1299, Sep....
6
votes
1answer
368 views
Matching/Assignment Problem
I'm not sure how I can represent and solve the following problem.
I have a list of sales (timestamp and quantity) and a list of corresponding inventory draws (timestamp and quantity). What I ...
6
votes
5answers
10k views
How to solve block tridiagonal matrix using Thomas algorithm
Thomas algorithm can be used to solve a tridiagonal matrix:
$$
\begin{bmatrix}
{b_ 1} & {c_ 1} & { } & { } & { 0 } \\
{a_ 2} & {b_ 2} & {c_ 2} & { } & { }...
1
vote
1answer
160 views
Pivoting in Block LU
What are common methods to choose pivot blocks in Block LU (for non-SPD/non-Diagonally Dominant Matrices)?
2
votes
0answers
83 views
Kernel independent fast multipole method for Yukawa potential [closed]
Has anybody used the KIFMM (https://web.stanford.edu/~lexing/fmm.pdf) for the Yukawa potential?
1
vote
2answers
76 views
Ranking Sewer Lines worst to best condition using Genetic Algorithm?
Problem
I work for a municipality and we are trying to figure out which sections of sewer lines to replace first or at least identify areas that should be looked at. It was suggested I use a Fast ...
1
vote
0answers
197 views
Use of Morton Key to reduce number of grid points
I asked a question on Stack Overflow Performance Issue with VP Trees and Nearest Neighborsand I was not satisfied with the answer and so I thought I would reword my question for this site and post ...
3
votes
0answers
93 views
First order methods for a large scale semidefinite program
I am interested in solving the following semidefinite optimization problem:
\begin{equation}
\begin{split}
\underset{X,\lambda}{\rm maximize} \;\;\;\;&\lambda^Tc \\
&-\mathbb{I} \le X \le \...
1
vote
1answer
66 views
Algorithm to find most similar elements in several groups
I'd like to find an algorithm that can solve the following problem:
Consider 4 groups of numbers:
Group 1: [10, 100, 1000],
Group 2: [101, 15, 2000],
Group 3: [20, 1500, 100],
Group 4: [150, 3000, ...
6
votes
2answers
2k views
An efficient way to numerically compute Stirling numbers of the second kind?
Is there an efficient way to numerically compute Stirling numbers of the second kind?
An approximate (not exact) method would suffice. Something similar to the connection between factorials and gamma ...
3
votes
1answer
87 views
What is a “good enough” method of assigning values to n variables subject to basic bounding constraints while maintaining relative weights?
Given triples of $n$ floating point values
$$(\min_1, \max_1, w_1), \dots, (\min_n, \max_n, w_n)$$
and a value $V$, what is a good algorithhm to assign values $v_i$ to each of the triples such that ...
1
vote
0answers
286 views
Maintain sorted ring buffer [closed]
I would like to insert elements into a ring (circular) buffer one at a time and maintain a permutation array which keeps track of the sorted elements in ascending order. To do this, I have adapted the ...
0
votes
1answer
464 views
Solving an equation in space and time using the Crank-Nicolson approach
Assume I have the following equation (light propagating in $z$-direction through the matter):
$$id_zu+d^2_ru=0$$
with $u(z, r)$ being a complex wave. The time scale in this equation is
$$t\equiv t_\...
5
votes
0answers
86 views
What Derivative-free optimization method should I use when my initial guess is very good?
I am trying to minimize a function where my initial guess is quite close to the minimum.
I'm trying to minimize
$$f(q) = \text{angle}(qw_1q*, v_1) + \text{angle}(qw_2q*, v_2) + \text{angle}(qw_3q*, ...
18
votes
1answer
634 views
Why are Octrees used for Multipole space decomposition?
In most (all?) implementations of the Fast Multipole Method (FMM), octrees are used to decompose the relevant domain. Theoretically, octrees provide a simple volumetric bound, which is useful for ...
1
vote
2answers
225 views
Effective way to build the neighbor's list in MD
I'm trying to implement the following form of the cell/neighbor list method in my MD code. I have divided my simulation box into a fixed number of cells, and according to its positions, I have ...
2
votes
2answers
110 views
Algorithm to construct all distances of a system described by $3N-6$ distances
A non-linear molecule has $3N-6$ degrees of freedom ($N$ is the number of atoms; ignoring translation and rotation). Therefore, a set of $3N-6$ distances and/or angles is enough, to describe the whole ...
6
votes
1answer
107 views
Stable computation of ratio of sums of large numbers
I have two sets of large positive numbers $a_1,\ldots,a_n$ and $b_1,\ldots,b_n$. By 'large' I mean of the order of $10^{10}$. I want to calculate the ratio $$R = \frac{a_1 - a_2 + \cdots +(-1)^{n+1}...
0
votes
1answer
156 views
Find hidden sequence $a_n = a_{n-1} + T $ , with period $T$, given some “random” numbers
I have this data plotted on a graph in which all points have the same value on the y-axis, e.g a constant integer "c", while the x-axis is the time in seconds.
So, for a c = 25 on the y-axis, there ...
4
votes
1answer
383 views
Using SVD to biorthogonalize left and right eigenvectors?
I have a set of left and right eigenvectors from an nonsymmetric eigenproblem, and I'd like to biorthogonalize them.
I tried Gram-Schmidt, but this fails for most cases.
I then read that the SVD is ...
5
votes
1answer
50 views
Transform from linear index of a packed triangular matrix to dense indices
Given indices $i,j$ s.t. $0\leq i \leq j <n$, the function $f(i,j)=i+j(j+1)/2$ maps 2d indices to linear indices in column major order. What is the fastest way to invert this function? My first ...
8
votes
0answers
106 views
Finding the smallest root of a function on $[0, \infty)$
I would like to find the smallest real root of a 1-D real-valued function $f(x)$ on the domain $x\in [0,\infty)$. In this problem, I can make the following guarantees on $f$:
$f$ does have a root at ...
2
votes
1answer
171 views
how to calculate the determinant of a projection of matrix to a subspace
I have a matrix $J$, and I know there are 3 existing zero eigenvalues and their eigenvectors. I want to detect if there is one extra eigenvalue to go cross zero (if it is zero, its eigenvalue will ...
3
votes
0answers
97 views
Fast Algorithms for the Simplicial Decomposition of a Convex Polytope in N-Dimensions
I'm in the process of constructing an algorithm which computes the Voronoi diagram of a set of points, but I now need a method to decompose each Voronoi cell into simplices. The information we have is:...
1
vote
0answers
147 views
Algorithm for group forming: as individual or in a preformed group
I have 20-80 users and 5-10 events with varying ranges of minimum and maximum number of free seats (2-4, 3-5, 2-6...). For example, with a range of 3-5 it is acceptable to only assign three users to ...
1
vote
0answers
59 views
Efficient initial identification of solid or liquid domains for a block structured Cartesian grid generation system
INTRO
Within the last 5 days I was able to generate a block structured Cartesian grid
generation system with a combination of Fortran,C++ and Python.
I am running intersection tests of the ...
1
vote
0answers
47 views
Space covering optimization
I have the following problem:
In the space $E=\{1, 2, \dots, N_x\} \times \{1, 2, \dots, N_y\}$, I want to define $N_R$ rectangles $R_k=\{x_k^0, \dots, x_k^1\}\times\{y_k^0, \dots, y_k^1\}$ which ...
1
vote
1answer
1k views
Simple finite volume method for compressible Navier-Stokes equations
I am interested in writing a simple, cell-centered, 2D FVM code for the unsteady, compressible Navier-Stokes equations (including shocks). Most of my experience is with finite difference and finite ...
3
votes
2answers
245 views
Image hash similarity matching possible?
I have the following question:
We have two face image files (JPEG), a Matrix of $128\times 128$ with values between 0-255.
We would like to hash both image files using a function $f(x, key)$. Where I ...
0
votes
1answer
217 views
Can I convert CUDA core to CPU core and use it as cpu core while running any program?
I was using Metatrader5 and have designed a strategy for trading using MQL5 programming language.
While I was running a Strategy Optimization process, I saw the it will need 10,00= iterations or ...
5
votes
1answer
214 views
Striking examples of success of local search algorithms
In N queens problem https://en.wikipedia.org/wiki/Eight_queens_puzzle, trying to find solution by backtracking encounters difficulties quite fast (even for SWI-Prolog, http://swish.swi-prolog.org/...
2
votes
1answer
612 views
MD Simulation: Reference for the Neighbor's List Method
With a rather basic knowledge in C++, I have written my own MD simulation code. Currently, I calculate forces in the most naive way: I go through all the atoms and account for their interactions. This ...
1
vote
1answer
42 views
Distribute sources among destinations
There are $n$ sources with the following positive volumes: $p_1, ..., p_n$ and there are $m$ destinations with the following positive volumes: $q_1, ..., q_m$. It is known that $p_1+ ...+ p_n=q_1+ ...+...
3
votes
1answer
108 views
Solve $A^{-1} b$ when one column is replaced
Given square matrix $A_0$, vector $b$, vector $A_0^{-1}b$ and matrices $A_1, A_2, \dots, A_k$, in which each $A_i$ is generated from $A_{i-1}$ by replacing one single column, I would like to find an ...
5
votes
0answers
66 views
Padua-type pointset for functions singular on line $x=y$
The Padua points $\mathrm{Pad}_{n} \subset [-1,1]^{2}$ are a unisolvent pointset with optimal growth of Lebesgue constant, described in detail here. With some work they can be used to generate a ...
3
votes
0answers
328 views
Open source implementation of Multiscale Combinatorial Grouping
I would like to use Multiscale Combinatorial Grouping for my PhD research. However, I am restricted to use open-source implementations and this one runs on Matlab.
Does anyone know of an equivalent ...
0
votes
1answer
218 views
CPU and GPU influence on task parallel execution performance
This question is mainly about hardware, but also about software.
In my current work I have approximately 68 millions of combinations that I am iterating through, in parallel. For each of those ...
1
vote
0answers
26 views
How does the MADS algorithm work in practice
Mesh Adaptive Direct Search (MASH) is an algorithm for black box optimization
I want to understand an implement this method to solve some 2D multivariate blackbox function $f(x,y)$, but am having ...
0
votes
1answer
78 views
Which are some good algorithms and heuristics to calculate the similarity between two matrices?
Say I have a matrix like this:
\begin{bmatrix}
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 1 \\
0 & 1 & 1 & 1 \\
\end{bmatrix}
And this one:
\begin{bmatrix}
...
4
votes
1answer
2k views
Applying the result of Cuthill-McKee in SciPy
I have applied SciPy's implementation of the Cuthill-McKee algorithm to a $48 \times 48$ sparse non-symmetric matrix in Compressed Sparse Row (CSR) format and the output is an array of length $48$ ...
5
votes
1answer
196 views
Efficient algorithm for a matrix product
Recall that a unit lower triangular matrix $L\in\mathbb{R}^{n\times n}$ is a lower triangular matrix with diagonal elements $e_i^{T}L e_i = \lambda_{ii} = 1$. An elementary unit lower triangular ...
0
votes
1answer
68 views
Adaptive gradient descent
I want to minimize some multivariable function $\Delta(\alpha, \beta)$. I know that this function has a zero point, $\Delta(5, 5) = 0$.
Starting from some $(\alpha, \beta)$ close to $(5,5)$ (e.g. (4....
1
vote
0answers
46 views
Finding “hidden” subassemblies: Suggestions for algorithms
I'm faced with an interesting problem and need some help finding existing best techniques to solve it. The setup is that we're analyzing a large system trying to find what I call "hidden subassemblies....
1
vote
0answers
96 views
Sequential Quadratic Programming for Quadratically Constrained Quadratic Programs
A standard Quadratically Constrained Quadratic Program (QCQP) is of the form:
$$ \underset{x}{minimize} \frac{1}{2}x^TP_{0}x + q_{0}^{T}x
$$
$$
subject \; to \quad \frac{1}{2}x^TP_{i}x + q_{i}^{...
2
votes
0answers
62 views
Parallel compact schemes using the Parallal Diagonal Dominant (PDD) algorithm
I would like to use the PDD algorithm developed by Sun to solve tridiagonal matrices in parallel for the following compact finite difference scheme:
$
\begin{align}
\dfrac{1}{4}f^{'}_{i-1} + f^{'}_i +...
1
vote
1answer
640 views
Iterative camera calibration - No convergence
I am trying to implement the algorithm from the research paper "Accurate Camera Calibration using Iterative Refinement of Control Points" from Datta et al.
Running many iterations does not show a ...
11
votes
2answers
6k views
How does the computational cost of an mpi_allgather operation compare with a gather/scatter operation?
I'm working on a problem that can be parallelized by using a single mpi_allgather operation or one mpi_scatter and one mpi_gather operation. These operations are called within a while loop, so they ...
