Questions tagged [algorithms]
A description of the specific steps needed to solve a particular problem in an unambiguous way, expressed in an abstract form.
126
questions with no upvoted or accepted answers
8
votes
0
answers
134
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
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
5
votes
0
answers
79
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 ...
- 2,125
5
votes
0
answers
109
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....
- 311
5
votes
0
answers
265
views
Sound Waves Simulation in 3D Environment
I want to do a simulation of sound waves including wave propagation, absorption, and reflection in 3D space.
I did some research and I found this question in stackoverflow but it talks about ...
- 151
5
votes
0
answers
2k
views
Two-chordless cycle extraction from a failed comparability graph recognition
I have implemented a comparability graph recognition algorithm from M.C. Golumbic's "Algorithmic graph theory and perfect graphs" book. It is hinted in Fekete, Schepers, and van der Veen's "Exact ...
- 590
4
votes
0
answers
549
views
Help with restart functionnality in sef-made GMRES solver in python
I am new to this forum and to computational science in general.
I started to learn numerical liner algebra on my own and would like to code a GMRES solver in python (no preconditioner for the time ...
- 201
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
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
4
votes
0
answers
173
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:...
- 41
4
votes
0
answers
469
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 ...
4
votes
0
answers
146
views
Stable computation of $\log\sum x_i$ from $\log x_i$, with many terms
Kahan's summation algorithm is a method to compute sums:
$$\sum x_i$$
with many terms, without significant error.
I want to do this with very large numbers, and instead of the numbers themselves, I ...
- 1,709
3
votes
0
answers
48
views
Does an alias method exist for sampling a discrete distribution that is slighlty modified at each iteration?
I have the following problem. I must sample from a discrete distribution that is changing at each sort.
Let me explain, with a "vivid" description, I draw a color ball from a bag. The ...
- 131
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
3
votes
0
answers
126
views
How can I evaluate the accuracy of my n-body simulation?
I am making an n-body simulation in python. There are many different methods to numerically solve the system of differential equations governing the gravitational interactions between the $n$ ...
3
votes
0
answers
120
views
Computing Algebraic Riccati inequality
In my Robust model control, I have got a couple of quadratic Riccati inequalities which need to be solved numerically on MATLAB. My question, Is there function on MATLAB can solve quadratic Riccati ...
- 31
3
votes
0
answers
338
views
logsumexp with one very large term and many very small terms
I want to compute an expression of the form:
$$L = \ln\sum_i e^{x_i}$$
Suppose that there are many small terms, say $e^{x_i} \approx \epsilon$. If there are $N_\epsilon$ such terms, their ...
- 1,709
3
votes
0
answers
102
views
Bracket Algebra, Straightening Algorithm
My apologies if the question is simple. I need to write a code for straightening algorithm. Which includes defining bracket algebra. I tried to write it in CoCoA-5, but it wasn't possible because ...
3
votes
0
answers
109
views
Find a function's minimizing set of parameters
I have a function defined by three parameters (or variables): $f(a,b,c)$ This function is not explicitly defined but is actually a piece of code which returns the result of fitting a curve $g(a,b,c)$ ...
- 131
3
votes
0
answers
115
views
Dissipation and symplectic manifolds
I'm working on an API for simulation of port-Hamiltonian systems. As far as I understand it, a Hamiltonian system is symplectic if it is power conserving, and so including resistive elements would ...
3
votes
0
answers
80
views
Parallel algorithm to use in place of PORTA?
We currently use PORTA software to find the list of facet-defining inequalities (FDI) for polytopes that we work with. For certain polytopes, PORTA works fine. But because it is a serial algorithm (...
- 31
2
votes
0
answers
22
views
Code to list all maximal bicliques of a bipartite graph
We are looking for a code to list all maximal bicliques in bipartite graphs efficiently, as we want to run it on (large and sparse) graphs, with up to roughly a million nodes and edges in no more that ...
- 21
2
votes
0
answers
62
views
How to implement a generic monte carlo algorithm for n-dimensional integration?
A very visual picture for Monte Carlo integration is the approximation of $\pi$, by sampling in a square which contains a quarter of the unit circle.
We can extend this picture to 3 dimensions, by ...
- 123
2
votes
0
answers
38
views
Cellular automata - can scaling factors that influence probability of spread be applied to rate of spread?
This is a follow-up question to my earlier question Stochastic cellular automata - algorithm limited by 1 cell per timestep. I am considering blending two approaches to a cellular automata model of ...
- 197
2
votes
0
answers
80
views
Multigrid method: linear solver and modified residual
I am trying to better understand the FAS multigrid algorithm for Euler equation in FV discretization. The usage of the modified residual (the residual with forcing) inside the different cases:
...
- 410
2
votes
0
answers
37
views
Scheduling Algorithm Goal is to Fix Max Number of Appointments
First post. Hi everyone.
I’m trying to develop an algorithm to later code that schedules appointments in a way such that the number of hours occupied by the appointments in a given day is maximized.
...
- 21
2
votes
0
answers
332
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 ...
- 131
2
votes
0
answers
74
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
2
votes
0
answers
236
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
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
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
2
votes
0
answers
74
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 +...
- 33
2
votes
0
answers
351
views
Finding integer/lattice points (coordinates) inside a polytope/polyhedra?
I am using Python but I wouldn't mind changing language. All I have gotten from my research are tools to count the number of (lattice) points inside a region given the equations for the planes that ...
- 121
2
votes
0
answers
70
views
Comparing the solutions to a multi-objective optimization problem
Suppose I have a multi-objective optimization problem, and I wish to find solutions using two different methods/algorithms. The result of each algorithms is a Pareto front. Comparing two different ...
- 215
2
votes
0
answers
267
views
sum of n numbers with the power k
I am searching for a good algorithm to solve problem 487 on project-euler. I dont want code or something like that, I only want the name of the algorithm thats best suited. Till now I think of either ...
- 21
2
votes
0
answers
111
views
Optimization based integration for MPM
I'm considering implementing (just for simplicity) the unconstrained implicit optimization based integration for Material Point Method as described in Chenfanfu Jiang's thesis on MPM (the minimization ...
- 175
2
votes
0
answers
250
views
Solving a 3D (almost radial) convolution with FFT
I have a 3D integral that is almost a radial convolution of the form
$$ \int d^{3}k'h(\mathbf{k'})g(|\mathbf{k-k'}|) $$
and I am looking for a fast and efficient algorithm (e.g. FFT) to solve it ...
- 21
2
votes
0
answers
47
views
Finding errors in frequency from a Fast Fourier Transform from Gaussian fitting
I took a FFT of sound in a box generated by a frequency sweep over a range of frequencies, and have an array of frequencies and their corresponding FFT amplitudes. According to models for the ...
- 131
2
votes
0
answers
56
views
SPECT reconstrction using MLEM
In Single-Photon Emission Computerized Tomography (SPECT) parallel beam reconstruction using Maximum-Likelihood Expectation–Maximization(MLEM), is it sufficient to scan the object around 180 degree? ...
2
votes
0
answers
1k
views
Exact line Search in Steepest descent
I wanted to clarify the idea of the exact line search in steepest descent method.
An exact line search involves starting with a relatively large step size ($\alpha$) for movement along the search ...
- 21
2
votes
0
answers
1k
views
Divide and Conquer division algorithm explained (as used in GMP bignum)
I am trying to understand the divide and conquer division algorithm that is used in the GMP bignum arithmetic library.
The code is very optimised and that makes it somewhat hard to understand. the ...
- 121
2
votes
0
answers
170
views
Area of convex n-dimensional polytope
I am looking for an efficient algorithm to calculate the surface area of an irregular N-dimensional polytope.
I have a description of this polytope both as coordinates of the vertices as as linear ...
- 21
2
votes
0
answers
96
views
Finding most efficient route (distance/number of nodes) that uses nodes at least X amount away from another node
I'm trying to find the "looped" route with the lowest value of D/n, where D=Distance, and ...
- 21
2
votes
0
answers
87
views
How to fix time intervals to store data in a stochastic simulation (continous time markov chain)
I am using FORTRAN to implement Gillespie's stochastic simulation algorithm. I would be running many simulations in parallel (both parallel instances with different seed and parallel functions); if I ...
- 143
2
votes
0
answers
114
views
Algorithm for optimizing graph interconnectivity
I have a partiuclar kind of graph problem and (not having a background in graph algorithms) I would like to know how this kind of problem is called in the literature and what algorithms exist for ...
- 435
2
votes
0
answers
252
views
Algorithms for adding hydrogens on a molecule
I want to add hydrogens to some linear polymer molecules (polyethylenes).
I know some working methods like using PyMOL internal function h_add. This method works, but hydrogens are added at distances ...
2
votes
0
answers
111
views
Preconditioner for large size hermitian eigenvalue problems
Basically I try to compute several smallest eigenvalues of some sparse 50k*50k eigenvalue problems using matlab.
$$Ax = \lambda Bx$$
With matlab eigs, it's not as fast as I expected. So I tried some ...
- 593
2
votes
0
answers
214
views
Good approximate solutions for a MILP problem
The company I work for has been developing an application for real-time control of sewer networks. Every 5 minutes, a MILP problem is built or updated, then solved using Gurobi.
For mid-sized cities, ...
- 153
2
votes
0
answers
124
views
Algorithm to distribute symbols uniformly in a square grid?
Given a square grid of size $n\times n$ and $m$ symbols (say for example, alphabets A, B, C...), having $N(i)$ number of $i$th symbol; $\sum_{i=1}^{m}N(i) = n\times n$. Is there any computationally ...
- 21