Questions tagged [algorithms]
A description of the specific steps needed to solve a particular problem in an unambiguous way, expressed in an abstract form.
468
questions
1
vote
0answers
60 views
How to approach geographic data interpolation by distance?
let's say I have a set of geographic locations (lat, lng) resulting from a query. Those locations have some kind of internal ranking, my set is sorted by this number in a descending order.
Now I'm ...
3
votes
1answer
62 views
Calculate Transformation Matrix between two sensors
My question is if I can calculate the transformation matrix between two sensors.
Each sensor provides a $4\times 4$ matrix for every timestep recorded.
The sensors are moving and have some noise in ...
0
votes
0answers
26 views
What is Voronoi particle tracking?
I've been trying to track this down, but google is giving paywall papers that don't appear to be directly related to computational science, or simply don't explain the source algorithm.
There's an ...
5
votes
1answer
75 views
Understanding butcher tableau when it comes to implicit methods
I've been learning about butcher tables and am having some difficulty understanding how to translate them when it comes to implicit methods. Specifically, I'm looking at backwards Euler:
\begin{array}...
2
votes
0answers
56 views
What exactly is the cause(s) of blow-up for too-large step size in a method like RK4?
I have been working on creating a few home-made numerical methods, and I am using them to visualize text-book problems from my Strogatz dynamics textbook. It feels like a good way to learn numerical ...
1
vote
0answers
40 views
Hybrid Ellpack-Itpack (ELL) + COO Sparse Matrix Representation decomposition threshold
Hybrid ELL-COO sparse matrix representation can be done as in the picture, I was looking intensively, however I couldn't find out what is the threshold of decomposing the original matrix into ELL part ...
3
votes
1answer
68 views
Efficient computation of leading eigenvector of a matrix product of the form $ADA^T$, where $D$ is diagonal
Let $A=[A_1|\ldots|A_m] \in \mathbb R^{n \times m}$ with $n \gg m \gg 1$ and $D=\text{diag}(d_1,\ldots,d_m)$ where $d_1,\ldots,d_m > 0$, and consider the $n\times n$ positive-definite matrix $X=\...
0
votes
0answers
26 views
solving electron motion in undulator by Boris method
I am trying to use Boris scheme to solve the electron trajectory in undulator.
The undulator field I used is:
$$B_x = b_0\sin(2\pi \tfrac{z}{\lambda_u})$$
where $b_0 = \dfrac{2\pi c_{0}K}{q m_{e} \...
1
vote
1answer
32 views
Weighted moving variance
i have a time-series and, in analogy with exponentially weighted moving average, i would like to compute the exponentially weighted moving standard deviation or variance in an efficient, numerically ...
0
votes
1answer
36 views
Dealing neighbor list in NVT Monte Carlo (MC) simulation
I'm making a NVT Monte Carlo (MC) simulation code with only short range interaction.
I found many MC tutorial codes (usually Lennard-Jones system) in online. However, most of them are doing energy ...
4
votes
2answers
113 views
Efficient algorithm to decide if a graph is a cactus?
A cactus is a connected graph in which every edge belongs to at most one simple cycle.
How should one modify the Depth First Search algorithm to obtain an efficient algorithm that determines if a ...
4
votes
1answer
81 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
29 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
27 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
103 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
42 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
70 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, ...
2
votes
1answer
66 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
46 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
117 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
120 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
35 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
74 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
74 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 ...
2
votes
0answers
26 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
17 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
58 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
454 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
77 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
73 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
104 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
180 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
78 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
164 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
63 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
82 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
83 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
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 ...
0
votes
2answers
137 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
49 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
100 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
86 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
56 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
44 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
185 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 ...
