Questions tagged [algorithms]
A description of the specific steps needed to solve a particular problem in an unambiguous way, expressed in an abstract form.
457
questions
4
votes
1answer
56 views
Fast algorithm for computing cofactor matrix
I wonder if there is a fast algorithm, say ($\mathcal O(n^3)$) for computing the cofactor matrix (or conjugate matrix) of an $N\times N$ square matrix. And yes, one could first compute its determinant ...
1
vote
1answer
28 views
How is the D value being updated at simple RRT algorithm?
I am studying the following lecture (image) regarding 5 iterations of the simple RRT algorithm.
I am trying to understand how each value is being updated regarding each iteration. I have figured out ...
0
votes
0answers
24 views
A preconditioner for self-consistent iteration
I tried to derive a preconditioner for self-consistent iteration similar
to section IX in arXiv:0804.2583.
For simplicity, consider here only
one orbital (one or two electrons) systems.
Suppose that ...
0
votes
1answer
69 views
Chip testing problem
An engineer has n supposedly identical integrated-circuit chips that in principle are capable of testing each other. The engineer test jig
accommodates two chips at a time. When the jig is loaded, ...
4
votes
1answer
36 views
Single-variable multimodal derivative-free optimization (for a well-behaved function)
Are there well-established approaches to single-variable multimodal optimization?
Given $f:\mathbb{R}\rightarrow\mathbb{R}$ that:
has several local minima within a given range of interest $[a,b]$
is ...
2
votes
1answer
66 views
How to justify using available code (in different language) for comparing algorithms
I have proposed an algorithm for a scheduling problem in a submitting paper. In the revision, the reviewer asked us to compare with another algorithm from the literature. Our algorithm is in MATLAB, ...
1
vote
1answer
54 views
How to find a pair of divisors as close as possible to each other?
For a given integer $n\in\mathbb{N}^*$, I want to find a pair $(x,y)\in{\mathbb{N}^*}^2$ such that $x*y=n$ and $|y-x|$ is as small as possible.
A naive algorithm I found is :
...
2
votes
0answers
45 views
Cover a polygon with least amount of parallelograms [closed]
I am solving the task that is as follows:
Input: a polygon. Can be any kind of polygon without self intersections. Can be a non-convex and with holes inside.
Goal: to cover it with 2 (at least) or ...
0
votes
1answer
112 views
Finding a shortest path in a graph
If each edge of a graph $G$ is unweighted or has equal weights, then the shortest path between two nodes in that graph is the path that contains the fewest number of edges. Such a path can be obtained ...
1
vote
3answers
106 views
Clustering with points lying along different 3D planes
I have a bunch of data points in 3D that lie along a few planes. What would be the best approaches to estimate the normals of these planes?
Edit: There are roughly equal number of points lying along ...
1
vote
0answers
33 views
How to numerically calculate the transition dipole integral in periodic systems?
Now I have wave functions $\psi_a$ and $\psi_b$ of two states in Gaussian CUBE format. I'd like to evaluate the transition dipole moment integral $\pmb\mu$ between these two states. As my simulation ...
0
votes
1answer
66 views
Stability of PDEs
I am currently trying to solve some PDEs with FiPy. At page 56, the manual mentions (https://www.ctcms.nist.gov/fipy/download/fipy-3.0.pdf).
The largest stable timestep that can be taken for this ...
0
votes
1answer
70 views
Python sequence cluster exercise
I am working through an exercise in my textbook and implementing the code in Python to practice dynamic programming. I feel like I am right on the edge of figuring it out, but after many hours, I come ...
1
vote
0answers
35 views
Number of $S_n$-orbits in $P^k(\{1,\dots,n\})$
This is a particular case of a question I asked on Mathematics Stackexchange, question which got no answer so far.
Let $n$ and $k$ be integers with $n\ge1$, $k\ge0$, and let $a(n,k)$ be the number of ...
1
vote
0answers
17 views
Piecewise-linear Continuations vs Marching Squares/Cubes
It seems that both piecewise-linear continuation and marching squares are methods to produce iso-contours of a scalar function given the function's values on a grid. It seems that piecwise-linear ...
0
votes
0answers
14 views
Finding Duplicate Pixel/Objects along Image seams
I have a seam of two images joined by merging algorithm that on occasion generates duplicated pixels/objects/artifacts on both sides of the seam. The images are large and currently the seams are ...
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 ...
3
votes
1answer
56 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
243 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
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
60 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
72 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
72 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
92 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
172 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
73 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
106 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
60 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
75 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
82 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*, ...
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
104 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
47 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 ...
7
votes
0answers
97 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
76 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
54 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
43 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
138 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
160 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
102 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 ...
2
votes
1answer
174 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
101 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
65 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
213 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
15 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
158 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
109 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
61 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....
