Questions tagged [algorithms]

A description of the specific steps needed to solve a particular problem in an unambiguous way, expressed in an abstract form.

Filter by
Sorted by
Tagged with
0
votes
0answers
17 views

Do the class of Construction Heuristic that does or does not change previous decisions have a name?

I'm writing a paper where I am discussing different types of construction heuristics. One type does not change previous decisions when adding new elements to the solution. I'd call them "...
3
votes
1answer
179 views

similarity/distance measurement between two ranked sequence

Is there an efficient way to measure similarity/distance between two sequences of ranked numbers/letters. The two sequences are of different length, and only have some elements in common? For example,...
3
votes
1answer
138 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 : ...
1
vote
2answers
144 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 ...
1
vote
0answers
29 views

Ising model in Python (Magnetization Scaling)

I am trying to implement the Ising Model in Python for Gibbs Distribution: $$\pi(x) = \frac{1}{Z(\beta)} e^{-\beta H(x)}$$ \begin{align*} p(x,y)&=r(x,y) \cdot \min \left( \frac{\pi(y)}{\pi(x)},1 \...
2
votes
3answers
238 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 ...
3
votes
1answer
393 views

Time Reversibility of Velocity Verlet Algorithm

I'm very new to computational Physics and am finding conflicting statements on whether the velocity Verlet algorithm, defined as: $\begin{align} x_{n+1} &= x_n + v_n \Delta t + \frac{1}{2} a_n \...
11
votes
4answers
458 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 ...
4
votes
3answers
134 views

Algorithms to generate spherical codes

A spherical code, specified by the parameters $(n,N,t)$, is a set of $N$ coordinates on the $n$-dimensional unit hypersphere such that the set of dot products between any two unit vectors from the ...
0
votes
1answer
107 views

Trouble Implementing 1d Wave Equation Finite Difference Solver

Im trying to solve the 1d Wave Equation on $x \in \mathbb{R}, t > 0$: $$u_{tt} = c^2u_{xx}, \hspace{5mm} u(x,0) = \cos(4 \pi x), \hspace{5mm} u_t(x,0) = 0$$ with $c = 1$ and a periodic boundary ...
2
votes
1answer
139 views

How to select initial time step in adaptive time step ODE solver (TR-BDF2)

The Problem I am currently reconstructing a TR-BDF2 scheme which contains the following two stages: \begin{align} y_{n+\gamma} & = y_n + \gamma \frac{h}{2}\left( f_n + f_{n+\gamma} \right) \...
3
votes
1answer
74 views

Maintain unitary time evolution for a nonlinear ODE

I want to solve a nonlinear ODE of matrix $A(t)$ $$\mathrm{i}\dot A = A(t)M(t),\:\mathrm{with}\: M(t)=A^\dagger(t)H(t)A(t)$$ where $H(t)$ and hence $M(t)$ are Hermitian. Therefore, I presume the time ...
0
votes
2answers
49 views

Technique or Pattern to calculate conditional statement

I am attempting to create a conditional statement that compares four (4) true/false conditions. Depending on the state of these four conditions (either true or false) the conditional statement will ...
5
votes
2answers
122 views

Exponent log to compute reciprocal power?

A MATLAB library seems to overcomplicate a computation: exp( (log(a) - log(b))/b ) which is mathematically equivalent (assuming real & positive ...
4
votes
1answer
58 views

Algorithm to merge two polygons (using connectivities)?

I am struggling with implementing an algorithm that does one simple thing: Consider two polygons (one can just draw any two polygons and number their vertices), whose connectivities in a node list are:...
3
votes
1answer
84 views

Understand the need for Welford's online algorithm

I am puzzled by the Wikipedia entry discussing many online algorithms for computing the sample variance, including the Welford's online algorithm. In particular, the sample variance $s_n^2$ can be ...
1
vote
0answers
34 views

Largest triangle that contains a point

Given the location of $n$ points on a 2D plane ($P_1, P_2, \ldots, P_n$); and the location of a special point $X$. Find three points $P_i,P_j,P_k$ ($i \neq j \neq k$) such that point $X$ is inside the ...
0
votes
0answers
30 views

Parameter sampling from a 3D isosurface in R

Before we start, a small disclaimer: I am not a computer scientist, and the field of isosurfaces is new to me, so hopefully, the question is phrased clearly:) Otherwise, let me know, and I will (try ...
1
vote
1answer
74 views

Transition from 2D to 3D finite element code, what are the inevitable modifications to be implemented?

Imagine we have a simple 2D FEM solver (we are dealing with solid mechanics) and we would like to develop it to a 3D FEM solver (let's say for the same solid mechanics problem) in this case what are ...
0
votes
0answers
40 views

Storing and retrieving two-dimensional and three-dimensional data

I work on computational geometry. A huge number of two-dimensional and three-dimensional data are found in my project. Coordinates of polygon and polyhedrons vertices consisted of two-dimensional and ...
7
votes
1answer
282 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 ...
3
votes
3answers
197 views

How to determine if 2 rays intersect?

We are given the 2D coordinates of 2 points: the first point is where the ray starts and it goes through the second point. We are given another ray in the same way. How do we determine if they have a ...
0
votes
0answers
50 views

Finding block structure of a tensor

Are there any well-known algorithms for partitioning a dense tensor into block-sparse form? In other words, I need to find a set of non-overlapping blocks that contain all non-zero entries of the ...
1
vote
1answer
59 views

Asymptotic complexity of fixed-rank SVD

According to the Wikipedia article on Singular Value Decomposition, the asymptotic complexity of computing the SVD of an arbitrary m×n matrix M with m>n by the popular Householder QR methods is O(...
3
votes
3answers
5k views

How to get ODE solution at specified time points?

The code below basically illustrates my problem. It is a test code for a pendulum. I solve it using a method suggested on https://stackoverflow.com/questions/12926393/using-adaptive-step-sizes-with-...
0
votes
1answer
151 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 ...
4
votes
1answer
88 views

Which algorithms(paper) should be reproduced by a student to enter the field of computational fluid-structure interaction?

We'd better not to reinvent the wheel. But without some programming, one can hardly understand computational fluid-structure interaction. And I would like to know which papers or algorithms should a ...
1
vote
0answers
29 views

Bipartite Euclidean Matching simple to implement approximate algorithm

I am looking for a simple to implement algorithm for the bipartite euclidean matching problem (or an implementation of any practical algorithm). I am aware of Agarwal's paper, but I would like to ...
1
vote
1answer
65 views

An efficient algorithm to find Nearest Neighbours

So imagine I have a $m$ vectors each of dimension $d$. Lets call them, $\vec x_{i}$, with $i = 1, 2, 3, 4, 5, \dots, m$. Now the idea is to find the neighbours of $\vec x_{i}$ (calling them $\vec x_{j}...
14
votes
4answers
25k views

The easiest way to find intersection of two intervals

Right now I stuck with a problem. It seems to be really trivial one, but still it is hard for me to find an appropriate solution. The problem is: One has two intervals and are to find the intersection ...
2
votes
3answers
309 views

On the reordering of sparse matrices

I have been reading on different techniques used to reorder sparse matrices to achieve better performance, the most popular being the Cuthill-McKee or Reverse Cuthill-McKee algorithm. Most of those ...
2
votes
0answers
99 views

Computing Singular Value Decomposition of small ($4\times 4$) matrices

I need to compute the Singular Value Decomposition (SVD) of many $4 \times 4$ matrices. I'm looking for SVD algorithms specialized for small matrices. I've read that the ...
5
votes
1answer
716 views

Cheap recalculation of eigenvalues and eigenvectors for a low-rank update of the matrix

Suppose I have a correlation matrix, $A$, and I already have the eigenvalues and eigenvectors of this matrix. For a given vector, $\mathbf{\mathit{v}}$, I want to calculate the eigenvalues and ...
3
votes
3answers
172 views

What are some algorithms to calculate the width of an arbitrary polygon when a bounding box approximation is inaccurate

What are some alternative algorithms to creating a bounding box for finding the max width of a concave, simple winding polygon, like the one in the below image? I prefer solutions that are more ...
0
votes
0answers
41 views

Producing Voronoi diagram in three dimensional

A Voronoi diagram is a kind of tesselation that divided the medium into polygons in 2D and polyhedrons in 3D. Although there are many algorithms to construct a Voronoi diagram, some of them are faster ...
0
votes
0answers
106 views

Explanation of Givens rotation in Jacobi Rotation SVD

I'm trying to implement Singular Value Decomposition (homework of sorts) via the Jacobi Rotation method (more info here, pages 11 and 12). I am stuck at the bullet saying (sorry for the picture, but I'...
0
votes
0answers
71 views

Derivative-free ill-conditioned non-linear least squares

I am looking for a package which can solve (non-linear) least squares problems without the use of derivatives (because of an expensive model), but which also deals with ill-conditioning well (such as ...
11
votes
2answers
33k views

What is the fastest algorithm for computing the inverse matrix and its determinant for positive definite symmetric matrices?

Given a positive definite symmetric matrix, what is the fastest algorithm for computing the inverse matrix and its determinant? For problems I am interested in, the matrix dimension is 30 or less. ...
2
votes
1answer
42 views

How do you construct a self-similar binary structured-tree?

Please excuse me if this question somehow looks trivial or not really interesting, but I recently have a hard time to convince someone else that my algorithm for constructing a self-similar binary ...
4
votes
2answers
581 views

Help understanding and implementing fast multipole method for N-body

I've been trying to understand the Fast Multipole Method but not really getting anywhere. It seems like the fastest mainstream N-body simulation algorithm, and I would like to implement it in an ...
4
votes
2answers
1k 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 ...
0
votes
0answers
25 views

Hawkes Process : recursive formula for : $R'_{m,n} (k) = \sum_{ \{i : t_i^n < t_k^m \} } (t_k^m - t_i^n) \exp ( - \beta_{m,n} ( t_k^m - t_i^n ) ) $

Following the advice of a fellow mathematician, I am asking my question here from (https://mathoverflow.net/questions/365554/hawkes-process-recursive-formula-for-r-m-n-k-sum-i-t-in-t) I need to use a ...
0
votes
0answers
51 views

Surface mesh from labeled 3D points

I'm trying to figure out how to create a surface mesh from a set of labeled 3D points. The 3D object could be something like part of a cave system or asteroid where there would be parts of the surface ...
2
votes
2answers
106 views

Using MILP to place a set of primers along a genome

Define variables $p_i,u_i\in\{0,1\}^G$, for $i=1,\ldots,8$ and $G=30000$. Let $v$ be a constant vector also in $\{0,1\}^G$, with approximately 25% of its entries equal to $1$ (randomly located). Let ...
1
vote
1answer
57 views

Newman algorithm yielding different result to what is given in his paper

Summary I am trying to implement Newman's algorithm for community detection, outlined in this paper. I am testing my implementation against one of the datasets used in that paper to benchmark the ...
1
vote
0answers
22 views

Combining many probabilities, modifying, seeking general formula

CONTEXT I need to combine the probability of occurrence of many thousands of events for millions of individuals (trees) in an agent-based/individual-based simulation model developed in NetLogo (agent-...
-2
votes
1answer
305 views

Multi-objective optimization problem - Euclidean space

I am looking for some clues for an optimization problem. My problem consists of arriving to a image by optimizing multiple layers with the pixel position probability. This is an overview of the ...
2
votes
1answer
69 views

Question regarding the energy computation of the Ising-Spin Model

In most of the Monte-Carlo-Algorithms I studied, I found, at the place where they compute the energy, always a line of code, where they divided by four. For example, this code-snippet is taken from ...
2
votes
1answer
114 views

Machine Learning for Optimization

I have a function which takes 100+ coefficients and outputs $x$. I wish to optimise $x$. Running the simulation 50 000 times will take around 15 minutes, however, this happens in parallel - and the ...
1
vote
0answers
52 views

Assume $AX = C$. How to determine which entry of $BX - D$ is non-negative?

Let $A,B$ be $n \times n$ matrices and $C,D$ be $n \times 1$ matrices. Moreover, all entries of $A,B,C,D$ are non-negative. Assume that there is a unique matrix $X$ that solves $AX = C$. My goal is ...

1
2 3 4 5
11