Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [algorithms]

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

7
votes
6answers
5k views

Python implementations of Gillespie's direct method

I'm looking for a decent implementation of Gillespie's Direct Method in Python, as if I code the algorithm myself I'm nigh positive I'll do it inefficiently. Anyone have a favorite?
-1
votes
0answers
81 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
27 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
34 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 ...
0
votes
3answers
282 views

Full segmentation of a linear space using a clustering algorithm

Once again, I am not entirely sure how to describe what I am looking for, hence I have a hard time finding answers using Google or any other literal search method. Let's say I have a time series: $$(...
2
votes
0answers
40 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 ...
7
votes
2answers
1k views

Markov (Chain) image generators?

Markov Chains can be used to generate, or auto-complete, text. https://en.wikipedia.org/wiki/Markov_chain#Markov_text_generators Training text is read, and some information about the text is ...
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 ...
3
votes
0answers
88 views

FFT-based Image Rotation Algorithms More Accurate Than Chirp-Z?

We're currently using a Chirp-Z based implementation: R. W. Cox and R. Tong, "Two- and three-dimensional image rotation using the FFT," IEEE Trans. Image Processing, vol. 8, no. 9, pp. 1297–1299, Sep....
5
votes
1answer
125 views

Eigenvector with maximum overlap

Given a matrix $M$ and a vector $v$, is there an efficient method to find the normalized eigenvector of $M$ that is closest to $v$, in that it has maximal overlap. More explicitly, a vector $v$ can be ...
6
votes
1answer
357 views

Matching/Assignment Problem

I'm not sure how I can represent and solve the following problem. I have a list of sales (timestamp and quantity) and a list of corresponding inventory draws (timestamp and quantity). What I ...
4
votes
5answers
8k views

How to solve block tridiagonal matrix using Thomas algorithm

Thomas algorithm can be used to solve a tridiagonal matrix: $$ \begin{bmatrix} {b_ 1} & {c_ 1} & { } & { } & { 0 } \\ {a_ 2} & {b_ 2} & {c_ 2} & { } & { }...
2
votes
1answer
67 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
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?
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 ...
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
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, ...
5
votes
2answers
1k views

An efficient way to numerically compute Stirling numbers of the second kind?

Is there an efficient way to numerically compute Stirling numbers of the second kind? An approximate (not exact) method would suffice. Something similar to the connection between factorials and gamma ...
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 ...
1
vote
0answers
49 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 ...
0
votes
1answer
318 views

Solving an equation in space and time using the Crank-Nicolson approach

Assume I have the following equation (light propagating in $z$-direction through the matter): $$id_zu+d^2_ru=0$$ with $u(z, r)$ being a complex wave. The time scale in this equation is $$t\equiv t_\...
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*, ...
18
votes
1answer
515 views

Why are Octrees used for Multipole space decomposition?

In most (all?) implementations of the Fast Multipole Method (FMM), octrees are used to decompose the relevant domain. Theoretically, octrees provide a simple volumetric bound, which is useful for ...
0
votes
0answers
35 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 ...
0
votes
2answers
79 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 ...
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 ...
6
votes
1answer
83 views

Stable computation of ratio of sums of large numbers

I have two sets of large positive numbers $a_1,\ldots,a_n$ and $b_1,\ldots,b_n$. By 'large' I mean of the order of $10^{10}$. I want to calculate the ratio $$R = \frac{a_1 - a_2 + \cdots +(-1)^{n+1}...
0
votes
1answer
152 views

Find hidden sequence $a_n = a_{n-1} + T $ , with period $T$, given some “random” numbers

I have this data plotted on a graph in which all points have the same value on the y-axis, e.g a constant integer "c", while the x-axis is the time in seconds. So, for a c = 25 on the y-axis, there ...
3
votes
1answer
264 views

Using SVD to biorthogonalize left and right eigenvectors?

I have a set of left and right eigenvectors from an nonsymmetric eigenproblem, and I'd like to biorthogonalize them. I tried Gram-Schmidt, but this fails for most cases. I then read that the SVD is ...
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 ...
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 ...
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
134 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 ...
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
1answer
924 views

Simple finite volume method for compressible Navier-Stokes equations

I am interested in writing a simple, cell-centered, 2D FVM code for the unsteady, compressible Navier-Stokes equations (including shocks). Most of my experience is with finite difference and finite ...
3
votes
2answers
106 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 ...
5
votes
1answer
150 views

Striking examples of success of local search algorithms

In N queens problem https://en.wikipedia.org/wiki/Eight_queens_puzzle, trying to find solution by backtracking encounters difficulties quite fast (even for SWI-Prolog, http://swish.swi-prolog.org/...
3
votes
1answer
70 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
149 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 ...
0
votes
1answer
128 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 ...