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
0answers
8 views

What kind of standard deviation must be used in optimization algorithms?

I would like to ask about the standard deviation of objective function value. There are two types of standard deviations ° Population standard deviation ° Sample standard deviation In ...
3
votes
1answer
32 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
61 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, ...
0
votes
1answer
40 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
44 views

Cover a polygon with least amount of parallelograms [on hold]

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
82 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
106 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
32 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
65 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
68 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 ...
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 ...
0
votes
0answers
13 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
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 ...
2
votes
0answers
164 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
56 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
72 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
72 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?
3
votes
1answer
86 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
163 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
66 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
93 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
59 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
71 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
82 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
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 ...
0
votes
2answers
91 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
47 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
94 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
75 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
52 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
0answers
136 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
150 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
98 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 ...
3
votes
1answer
148 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 ...
5
votes
0answers
65 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 ...
4
votes
0answers
202 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 ...
1
vote
0answers
13 views

How does the MADS algorithm work in practice

Mesh Adaptive Direct Search (MASH) is an algorithm for black box optimization I want to understand an implement this method to solve some 2D multivariate blackbox function $f(x,y)$, but am having ...
0
votes
1answer
149 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 ...
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 ...
0
votes
1answer
61 views

Adaptive gradient descent

I want to minimize some multivariable function $\Delta(\alpha, \beta)$. I know that this function has a zero point, $\Delta(5, 5) = 0$. Starting from some $(\alpha, \beta)$ close to $(5,5)$ (e.g. (4....
1
vote
0answers
46 views

Finding “hidden” subassemblies: Suggestions for algorithms

I'm faced with an interesting problem and need some help finding existing best techniques to solve it. The setup is that we're analyzing a large system trying to find what I call "hidden subassemblies....
1
vote
0answers
65 views

Sequential Quadratic Programming for Quadratically Constrained Quadratic Programs

A standard Quadratically Constrained Quadratic Program (QCQP) is of the form: $$ \underset{x}{minimize} \frac{1}{2}x^TP_{0}x + q_{0}^{T}x $$ $$ subject \; to \quad \frac{1}{2}x^TP_{i}x + q_{i}^{...
2
votes
0answers
55 views

Parallel compact schemes using the Parallal Diagonal Dominant (PDD) algorithm

I would like to use the PDD algorithm developed by Sun to solve tridiagonal matrices in parallel for the following compact finite difference scheme: $ \begin{align} \dfrac{1}{4}f^{'}_{i-1} + f^{'}_i +...
1
vote
1answer
409 views

Iterative camera calibration - No convergence

I am trying to implement the algorithm from the research paper "Accurate Camera Calibration using Iterative Refinement of Control Points" from Datta et al. Running many iterations does not show a ...