# Questions tagged [algorithms]

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

574 questions
Filter by
Sorted by
Tagged with
73 views

### What is fastest method for finding the minimum and maximum eigenvalues of a (possibly very large) symmetric matrix?

What is the best way to find the extreme eigenvalues - in order to find the spectral radius - of a general real dense symmetric matrix? Looking at similar questions e.g.: What's the most efficient ...
• 21
344 views

### Non-uniform Gaussian spaced vector

I am working on a Fortran code that uses a uniformly spaced grid in two directions (x,y). Which works fine, but when I need to study a certain problem with good resolution, I need to increase the ...
• 43
86 views

### An alternative to Levenberg–Marquardt algorithm

When trying to solve for a (over)determined non-linear least square method: $$\underset{x}{\min}||f(x)||^2_2, f: \mathbb{R}^n \rightarrow \mathbb{R}^m, x\in \mathbb{R}^n, m\geq n$$ we use the Gauss-...
44 views

### Standard deviation for online scenarios

Let's suppose you have to create an online algorithm $f(x_i)$ that will return the average ($\mu$); And the standard deviation ($\sigma$); Of numbers $x_0, \dots, x_i$. A straightforward approach ...
20 views

### Find clusters with threshold for number of members

I need to find clusterization of some daily weather data, and the number of days in any cluster should be more than some threshold (e.g. 30). So if some cluster has less members, it has to be merged ...
• 101
78 views

### Computing the Fiedler vector of a large, sparse graph

I have a sparse, undirected and unweighted graph $G$ of size $n$, with $n$ on the order of say several million. I would like to compute the Fiedler vector $f$ of $G$, which is the eigenvector ...
• 503
1 vote
85 views

### Regarding the difference between Metropolis-Hastings and Wolff algorithm (synchronous vs asynchronous) applied to Ising Model?

I am trying to self-learn concepts at the intersection of physics and programming. When reading up on the Ising Model, I find that the typical programming tutorial (such as this one) covers the ...
109 views

### Gradient descent for solving polynomial equations while encouraging variables to be nonzero

I would like to use gradient descent to "randomly sample" solutions to a set of homogeneous polynomial equations. Because the equations are homogeneous, setting all variables to 0 is a valid ...
• 123
1 vote
220 views

### Why algorithm is computational procedure?

I am reading a book: Introduction to Algorithms. In the first chapter is itself, Algorithm is defined as ...
• 109
39 views

### Methods for delaying the "break" in non-linear least squares optimisation when the step size gets too small?

I am using the Levenberg-Marquardt method for calibration purposes. Typically, the RMSE of my calibration looks like: I want to break the algorithm when the algorithm step-updates start to slow down, ...
3k views

### More stable algorithm to calculate sqrt(a^2 + b^2) - abs(a) in MatLab

Suppose we want to calculate $\sqrt{a^2+b^2}-|a|$ in MatLab. Using sqrt(a^2 + b^2) - abs(a) will have some problems: If a or <...
9k views

### stupid + stupid = brilliant in scientific computing

I'm interested in examples of very effective methods in scientific computing that are the sum or naive combination of very ineffective or bad ones.
• 10.3k
120 views

### Algorithm to solve system of nonlinear equations

I would like some tips in figuring out a good algorithm to find the solution of the following system. Let $\theta$ be a constant in $(0,1)$, let $i,l=1,...,N$, let $a_{l}$ and $b_{i,l}$ be some ...
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
1 vote
91 views

### Can I find sines or cosines of rational parts of π without using radians? If not, how do I reduce the errors caused solely by the transcendence of π?

this may be irrelevant for people who need fast code. But for me it's just the opposite -- i.e. in the specific situations when I know that the extra time allows me to make my calculations more ...
31 views

### What do the Max-Cut algorithm graph cuts mean?

The max-cut algorithm divides a graph into 2 subsets, for instance: While I understand the algorithm, I do not quite understand the meaning of the result. In the above picture, what does the ...
• 101
107 views

### Algorithm about finding a combination that the sum is closest to a given number

Given a matrix $P\in \mathbb{R}^{n*k}$ (just for ease of notation, no matrix or linear algebra is actually needed; bound to $(0,1)$ if necessary), select one number from each row and compute the sum. ...
• 141
1 vote
78 views

### Rayleigh-Ritz under LOBPCG : Nested iteration?

I am trying to understand the basic LOBPCG algorithm, as used in popular python libraries, primarily from the suggested resource on wiki. LOBPCG involves a subroutine to compute the coefficients of ...
• 11
1 vote
77 views

### Why is the definition of convergence different for root finding algorithms as compared to sequences?

The definition of convergence for root finding algorithms is given in a few sources as: A sequence ${x^k}$ generated by a numerical method is said to converge to the root $\alpha$ with order $p\geq 1$ ...
79 views

### On solving a first order nonlinear differential equation

It all starts with this Cauchy problem: $$\begin{cases} \sin(2x(t)) -\cos(3x'(t)) = x(t) + x'(t) \\ x(0) = 1 \\ \end{cases} \quad \quad \text{with} \; t \in [0,10]\,.$$ Not knowing which way to turn,...
• 113
44 views

### Looking for an algorithm to find points where lines intersect most frequently

I have a file that contains the coordinates of two points that make up a line. When I plot these lines, I notice that there are areas where the lines intersect more often. These points are identified ...
31 views

### How is the transfer function of a state-space representation numerically computed?

This question is a duplicate of this question that I asked on dsp stack exchange. However, nobody had the answer there but the question seems more appropriate on this forum (If not feel free to tell ...
• 101
1 vote
908 views

### What are the benefits of cutting by half the number of multiplications needed to calculate n?

First we need to present the details of what makes that cut possible. The issue is linked to the sum of squares $1^2+2^2+3^2+4^2+...+n^2$. We consider the two cases: 1-the case of a sum of even ...
• 139
285 views

### Is it really necessary to solve a system of linear equations in the Finite Element Method?

When we solve some boundary value problem by Finite Element Method, the appropriate system of linear equations is built, $$Ax=b.$$ Usually we use the solution x just for plugging it into some ...
1 vote
43 views

### Simulating Quantum Wave Function/Schrodinger Equation With A Time Varying Potential

I have solved the Time Independent Schrodinger Equation using the Numerov method and diagonalizing the Hamiltonian, in 1 - 3 dimensions. I suppose I could time-evolve it by multiplying every element ...
• 33
118 views

### Open source implementations of the medial axis transform for vector shapes

Are there any open source implementations of the medial axis transform for vector shapes? I have searched without finding any useful results. It seems that CGAL library doesn't have it implemented nor ...
• 101
129 views

### how to generate the Laplacian most efficiently

I have a cubic lattice $L_1\times L_2 \times L_3$ with the periodic boundary condition. I have to construct the Laplacian matrix in the sparse format. My matlab code is like this ...
• 123
1 vote
81 views

### Generating highly gzip-compressible, low entropy text that looks random-ish

I'm searching for an algorithm that can generate a set of 500 to 2000 characters from the alphabet a-z, A-Z, 0-9 (no interpunctuation) where the set has the following properties: highly compressible ...
1 vote
32 views

### Mass spectrometer atomic species identification

I'm starting to look at ways to analyze the output of a mass spectrometer. My first searches led to some white papers far from what I'm looking for (complex molecules vs simple atoms for me). With ...
• 111
1 vote
214 views

### How to find an alignment between two overlapping time series?

Context I'm working with absorbance spectral data. I have two spectra generated for a single analyte. Each spectrum was collected over two overlapping wavelength regions e.g. 8-10 micron and 9-11 ...
9k views

### How do compression algorithms compress data so fast?

I've come across compression algorithms, I tried creating a simple run-length encoding algorithm but I notice that when I searched other algorithms I was shocked to know that some algorithms can ...
• 153
1 vote
165 views

### Viterbi algorithm for object tracking

I want to solve a problem of object tracking along time. The problem is - I have a sequence of images, and I need to find and track the creation of the objects, than their movement, and than their ...
• 11
62 views

### Is there an efficient way to loop through this problem? [closed]

So I saw this very interesting problem. Let's say you have a length of 2, and a base length of 5 l = 2, b = 5 this would be translated to : ...
• 153
51 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
2k views

### Is there an algorithm or graph theory that allows me to not need to store an intermediate matrix when calculating AT*Y1*A + BT*Y2*B?

I have a system of conductors for which there are two dense matrices of the (complex) mutual admittances, $Y_A$ and $Y_B$, which are symmetric. Then, an equivalent nodal admittance matrix $Y_N$ is ...
709 views

### Solving the time dependent Schrödinger equation with leapfrog integration in 1D

To my frustration I am struggling to implement leapfrog integration for the time dependent Schrödinger equation. To the best of my knowledge this was first explicitly done in "A fast explicit ...
• 229
109 views

### Recursion relations for integrating Gaussian functions

I'm trying to implement a numerical method used in quantum chemistry from scratch. I'm using this paper as a reference. It's also available on Sci-Hub. So, the method requires calculating integrals of ...
217 views

### Which optimization algorithm to max a single parameter by searching a landscape of five parameters?

Background: We're operating a small betatron which makes use of a vacuum tube where electrons are accelerated circularly. First, they get injected (like inserted) and contracted (like squeezed). After ...
• 133
109 views

### Quasi-Newton Method with a Transformed Hessian

I've recently came across an implementation of the BFGS algorithm but it has an additional step where the Hessian is transformed after the each update. This transformation is done so that certain ...
• 123
666 views

### Which algorithms exist to create a tetrahedral volume mesh from an STL file?

Basically just that. I am trying to write a C++ program that reads in an STL and should compute an unstructured tetrahedral volume mesh based on the surface triangulation given by the STL file. I ...
68 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
27 views

### calculate order difference between 2 arrays (global and local)

Actual Problem: I want to assess the difference in two text rewrites: it can be fine today => today, it can be fine Simplified Problem: ...
2k views

### Solve a large-scale linear system of equations with millions of unknowns

I have a large-scale system of linear equations: $Ax = b$, where $A$ is an $n\times n$ square symmetric positive definite matrix (not sparse), $b$ is an $n \times 1$ vector and $x$ is $n\times 1$ ...
1 vote