# 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
Filter by
Sorted by
Tagged with
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
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
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
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
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
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 ...
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 ...
107 views

• 141
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:...
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 ...
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
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
176 views

### First order methods for a large scale semidefinite program

I am interested in solving the following semidefinite optimization problem: \begin{split} \underset{X,\lambda}{\rm maximize} \;\;\;\;&\lambda^Tc \\ &-\mathbb{I} \le X \le \...
• 31
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$ ...
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
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
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 ...
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
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 ...
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
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
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
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
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
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
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
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 ...
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
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
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