Questions tagged [algorithms]
A description of the specific steps needed to solve a particular problem in an unambiguous way, expressed in an abstract form.
569
questions
7
votes
1
answer
246
views
Numerically stable and fast sum of last K elements in sequence
Suppose I have a long, possibly infinite, sequence $x := [x_1, x_2, ...]$, and I want to use it to compute another sequence $y:=[y_1, y_2, ...]$ where each element is the sum of the last K elements of ...
- 171
5
votes
0
answers
106
views
Efficient way to find eigenvalues of complex symmetric matrix with real off-diagonal elements
My goal is to find all eigenvalues (and eigenvectors) in a given range of magnitudes of a complex symmetric matrix with real off-diagonal elements (only diagonal elements are complex). Currently I'm ...
- 151
2
votes
0
answers
75
views
Alternatives to breadth-first-search in 3D grid cluster detection?
I've got a question about a good way to find the quickest algorithm for my problem:
problem:
I've got a 3D cubical grid containing voxels that are either 1 or 0. It is stored as a flattened array. If ...
- 121
2
votes
0
answers
45
views
Evaluating integral $F(r_2) = \frac{1}{r_2^n} \int_0^{r_2} r_1^n f(r_1)\ \mathrm{d}r_1$ without growing instability
I have the following expression to be numerically integrated in a vector-based library (e.g. numpy, MATLAB, etc),
$$
F(r_2) = \frac{1}{r_2^n} \int_0^{r_2} r_1^n f(r_1)\ \mathrm{d}r_1,
$$
where $n$ is ...
- 181
1
vote
0
answers
35
views
SHREC 2010 Descriptors
I will appreciate if I may find someone how can clarify for me the part regarding the quality of feature descriptor, shown in the figure below:
and this screenshot is from the article: SHREC
All my ...
- 43
3
votes
1
answer
375
views
Evaluate 3D Shape Descriptor
I'm trying to create my own 3d shape descriptor, the idea is that how I may evaluate how much my descriptor is well and good?
What I checked is that they evaluate descriptors through shape matching, ...
- 43
4
votes
0
answers
107
views
Computation of Troullier-Martins pseudowavefunctions
The computation of Troullier-Martins pseudo-wavefunctions has been
described in [1].
The pseudo-wavefunction $R^{\textrm{PP}}_l$ is defined by
$$
R^{\textrm{PP}}_l(r) =
\left\{
\begin{array}{ll}
R^{\...
- 331
12
votes
4
answers
528
views
Should benchmarkings be done at all? What is the point?
I am reading a paper which compares algorithm A versus algorithm B.
It shows that algorithm A is faster than algorithm B via benchmarking that shows the CPU time.
What is the point of this? Any ...
- 121
1
vote
0
answers
77
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 ...
- 11
3
votes
1
answer
445
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 ...
user33278
0
votes
1
answer
621
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 ...
- 161
6
votes
1
answer
957
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}...
- 183
2
votes
0
answers
240
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 ...
- 183
1
vote
0
answers
195
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 ...
- 113
3
votes
1
answer
145
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=\...
- 165
1
vote
1
answer
715
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 ...
- 131
1
vote
2
answers
294
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 ...
- 11
6
votes
2
answers
521
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 ...
- 63
5
votes
1
answer
1k
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 ...
- 53
1
vote
1
answer
42
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 ...
- 221
0
votes
0
answers
48
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 ...
- 331
0
votes
1
answer
1k
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, ...
- 9
4
votes
1
answer
179
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 ...
- 255
3
votes
1
answer
140
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, ...
- 133
4
votes
2
answers
272
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 :
...
- 141
2
votes
0
answers
65
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 ...
- 121
0
votes
1
answer
326
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
2
votes
3
answers
381
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 ...
- 29
1
vote
0
answers
118
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 ...
- 111
0
votes
1
answer
125
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 ...
- 101
0
votes
1
answer
129
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 ...
- 103
1
vote
0
answers
42
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
0
answers
41
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 ...
- 251
0
votes
1
answer
29
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 ...
- 101
3
votes
1
answer
461
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 ...
- 31
4
votes
1
answer
3k
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 ...
- 41
2
votes
0
answers
60
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, ...
- 153
0
votes
1
answer
68
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 ...
2
votes
1
answer
458
views
Pivoting in Block LU
What are common methods to choose pivot blocks in Block LU (for non-SPD/non-Diagonally Dominant Matrices)?
8
votes
1
answer
636
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,855
1
vote
0
answers
225
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 ...
user16555
3
votes
0
answers
176
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 \...
- 31
1
vote
0
answers
541
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,048
1
vote
1
answer
214
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, ...
- 13
3
votes
1
answer
96
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 ...
- 151
4
votes
0
answers
97
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*, ...
- 141
1
vote
2
answers
78
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 ...
- 111
2
votes
2
answers
634
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 ...
- 187
5
votes
1
answer
143
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 ...
- 233
8
votes
0
answers
135
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 ...
- 725