Questions tagged [algorithms]
A description of the specific steps needed to solve a particular problem in an unambiguous way, expressed in an abstract form.
-1
votes
0answers
79 views
Optimal way of comparing the lines of different files
I have 1600 ASCII files with 1000 lines in each file. Each line has only one entry and is a floating point number e.g. 1.67923.
Let's denote the line1 of file1 with ...
0
votes
1answer
19 views
Binary tree for 2 elements [closed]
I want to understand Binary Search for 2 element list made of 1,2. I draw a tree as below. Is it correct?
If I want to search for an element 2, it will make 2 comparisons. If I want to search for ...
-1
votes
0answers
25 views
Non-Linear Optimization Using NLOPT library in C++
NLOPT (Non-linear optimisation library) clearly mentions that non-linear constraints may not be satisfied at an intermediate step of optimisation, but if one uses maxeval() function as stopping ...
1
vote
1answer
33 views
Radiation heat transfer between surfaces
I'm trying to model the temperature distribution over a curved surface. Apart from the heat equation, I need to take into account the energy emission/absorption through electromagnetic radiation. The ...
2
votes
0answers
37 views
Discrete-time Algebraic Riccati Equation (DARE) solver in C++
I need to use a Discrete-time Algebraic Riccati Equation (DARE) solver for an embedded controller (with limited processing power) in a research project and sadly, I can't find any implementation of it ...
2
votes
0answers
54 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
55 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 ...
1
vote
1answer
61 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
64 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?
2
votes
1answer
66 views
Accurate and efficient computation of the inverse Langevin function
The Langevin function $\mathcal{L}(x) = \mathrm{coth}(x) - \frac{1}{x}$ occurs in computations related to elastomers and paramagnetic materials. It is easily computed accurately and with high ...
1
vote
0answers
148 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
58 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
0answers
46 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 ...
1
vote
1answer
52 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, ...
3
votes
1answer
64 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 ...
4
votes
0answers
76 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*, ...
0
votes
0answers
34 views
Stochastic simulation Gillespie algorithm for areas instead of volumes?
I am trying to find resources on the Gillespie stochastic simulation algorithm for my system which happens on a surface. The original algorithm was developed for a reactor of volume $V$, but my system ...
1
vote
2answers
75 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 ...
0
votes
2answers
78 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 ...
5
votes
1answer
45 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 ...
6
votes
0answers
90 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 ...
3
votes
0answers
70 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
44 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
39 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
0answers
132 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 ...
3
votes
2answers
103 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
86 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 ...
3
votes
1answer
69 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
40 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
100 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
60 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
147 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 ...
1
vote
0answers
12 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
127 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 ...
2
votes
2answers
108 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 ...
0
votes
1answer
60 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....
2
votes
0answers
40 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
54 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
51 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
317 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 ...
2
votes
1answer
82 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 ...
6
votes
0answers
110 views
Element-wise thresholding a low-rank matrix in O(n) time?
Define the element-wise thresholding operator $T_\tau(\cdot)$ with threshold $\tau$ as
$$ [T_\tau(X)]_{i,j} = \begin{cases} X_{i,j} &\mbox{if } |X_{i,j}| \ge \tau, \\
0 & \mbox{if } |X_{i,j}|...
1
vote
0answers
101 views
Finding integer/lattice points (coordinates) inside a polytope/polyhedra?
I am using Python but I wouldn't mind changing language. All I have gotten from my research are tools to count the number of (lattice) points inside a region given the equations for the planes that ...
1
vote
0answers
44 views
find vector that minimize the (W-A*B)
I want find candidate of B vector that
$$min|(W - A_i * B_i)|$$
$$ a_i > 0,\ A_i=\{a_0,...,a_i\},\ B_i=\{-1,0,1\}^i$$
for example, given
$$W = 0.6$$
$$A_4 = [0.1, 0.2, 0.4, 0.7] $$
one of answer ...
0
votes
1answer
59 views
Approximation diameter 2-dimensional space
If I have a set A constituded by $n$ 2-dimensional points, how can I find a $\sqrt{2}$-approximation diameter of A, that is the maximum Euclidean distance between any two points in A, in linear time?
...
2
votes
1answer
66 views
Union of closed intervals on $\mathbb{R}$
Suppose there are multiple intervals on $\mathbb{R}$, e.g., $[0,0.5]$, $[0.4,1]$, $[1.5,2]$, the union of them should be $[0,1]$ and $[1.5,2]$. Is there a specific datastructure (or algorithm) for ...
2
votes
2answers
104 views
Find connected circles
I have a problem as follows:
We have a set of circles (we know the radius r and the center point c in Rd of each circle)
We ...
0
votes
1answer
64 views
Linear algebra of the inertial partition algorithm
You can find the description of the inertial partition algorithm either in [1] or [2].
I think, I understood the main idea behind this algorithm:
We have the spatial coordinates of points that ...
0
votes
1answer
65 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}
...
1
vote
1answer
51 views
An algorithm to calculate $R_n$s from this recursive equation
How can I write an algorithm to calculate $R_n$s for any desired $n$ from the following equation with given $f,R_0$?
So the output of the code would be $R_1,R_2,...$
$$R_n^2-2fR_n=R_0^2-2fR_0+\sum_{...
