Stack Exchange Network

Stack Exchange network consists of 175 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.

0
votes
1answer
58 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
votes
0answers
22 views

Tracking fluid movement in a pipe

I have a general question regarding developing an algorithm for a problem that has come up. I need to track fluids of different densities as they travel down a pipe in a well, then come back again to ...
1
vote
0answers
33 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
16 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 ...
6
votes
1answer
208 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 ...
3
votes
1answer
55 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
0answers
12 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 ...
1
vote
0answers
42 views

GMRES algorithm and Krylov base

I have a question about the precision of the GMRES algorith and its variation a s a function of the size of the Krylov subspace. I want to solve a Poisson equation using a spectral method. My problem ...
0
votes
3answers
289 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: $$(...
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?
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 ...
2
votes
0answers
89 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
55 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
58 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
92 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....
6
votes
1answer
359 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
77 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
69 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
68 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
158 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
64 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
56 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
67 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
72 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
337 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
78 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
519 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
2answers
81 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
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 ...
6
votes
1answer
85 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
155 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
276 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
46 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
91 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
74 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
46 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
42 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
972 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
132 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
91 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 ...
6
votes
1answer
161 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
100 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
41 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 ...