As of May 31, 2023, we have updated our Code of Conduct.

Questions tagged [algorithms]

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

Filter by
Sorted by
Tagged with
0 votes
0 answers
35 views

Is it possible to calculate a true win rate at Gates of Olympus? [closed]

I often see bloggers on youtube winning large sums of money. I was interested in the game Gates of Olympus because it seems to be more popular. I entered its name into a youtube search, and almost all ...
user45701's user avatar
3 votes
1 answer
61 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. ...
obfish's user avatar
  • 131
1 vote
0 answers
44 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 ...
Shark's user avatar
  • 11
1 vote
2 answers
59 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$ ...
Username_57's user avatar
0 votes
0 answers
24 views

General dimensional solution to fast sweeping quadratic equation

I am reading Hongkai Zhao's paper The Fast Sweeping method. I have implemented the method in 2D and now I want to move onto 3D. However section 2.6 confuses me. The article says: But I have no idea ...
Makogan's user avatar
  • 259
0 votes
0 answers
54 views

Is it normal for a genetic algorithm to not have mating phase?

I know that is possible for a genetic algorithm to not have a mating phase because some genetic algorithms use a "mutation-only" approach, where new candidate solutions are generated by ...
noob234's user avatar
  • 101
0 votes
1 answer
63 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,...
Monster's user avatar
  • 103
0 votes
0 answers
34 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 ...
ConfusedStudent's user avatar
0 votes
0 answers
30 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 ...
NokiYola's user avatar
  • 101
1 vote
2 answers
403 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 ...
user25406's user avatar
  • 129
3 votes
1 answer
226 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 ...
Fidel Pestrukhine's user avatar
1 vote
0 answers
37 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 ...
cgbsu's user avatar
  • 33
0 votes
0 answers
68 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 ...
Amazigh_05's user avatar
2 votes
1 answer
87 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 ...
poisson's user avatar
  • 123
1 vote
1 answer
62 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 ...
Roger Goodman's user avatar
1 vote
0 answers
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 ...
dargaud's user avatar
  • 111
1 vote
0 answers
113 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 ...
nlivingstone's user avatar
12 votes
6 answers
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 ...
gushkash's user avatar
  • 153
1 vote
1 answer
104 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 ...
josh95's user avatar
  • 11
-1 votes
1 answer
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 : ...
gushkash's user avatar
  • 153
3 votes
0 answers
43 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 ...
Stef1611's user avatar
  • 131
9 votes
2 answers
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 ...
Pedro H. N. Vieira's user avatar
2 votes
1 answer
443 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 ...
Martin C.'s user avatar
  • 215
0 votes
0 answers
61 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 ...
Dmitry Govorov's user avatar
3 votes
1 answer
179 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 ...
Ben's user avatar
  • 133
2 votes
1 answer
103 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 ...
Unskilled's user avatar
  • 123
0 votes
2 answers
341 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 ...
SarahJuliet1510's user avatar
2 votes
0 answers
53 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 ...
infinitezero's user avatar
-1 votes
1 answer
25 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: ...
Kevin Danikowski's user avatar
0 votes
1 answer
563 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$ ...
Math_Lover's user avatar
1 vote
0 answers
75 views

Generate polynomial basis through a sequence of SVD

I need help to understand how to use the result given by an algorithm for constructing an orthonormal polynomial basis over $L^{2}(X)$, where $X\subset\mathbb{R}^2$, with respect to the inner product $...
Raibyo's user avatar
  • 219
1 vote
1 answer
94 views

Fast algorithm to compute chi-square

I would like to evaluate the chi-square of the form $\chi^2=v^{T}C^{-1}v$ where $v$ is a column vector and $C$ is a covariance matrix. Both $v$ and $C$ are known and $C$ is a $740\times740$ matrix. ...
user7896's user avatar
  • 123
1 vote
1 answer
55 views

Why does this implementation for Eisenstein integer pairs of Euclid's method for finding greatest common denominators get stuck for this one point?

My Math SE question determining if a coincident point in a pair of rotated hexagonal lattices is closest to the origin? explains the problem I have. I won't reproduce the whole thing in detail here, ...
uhoh's user avatar
  • 1,006
2 votes
0 answers
37 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 ...
Seth Lutske's user avatar
2 votes
1 answer
256 views

Finding all valid combinations of numeric inputs and operators in a Reverse Polish Notation expression

An arithmetic expression written in Reverse Polish (postfix) Notation is an ordered list of numbers and algebraic operators, which are sequentially evaluated as a stack would process them to return a ...
Retired_Scripter's user avatar
1 vote
1 answer
227 views

Schrodinger's Equation differential

I am working on a modified version of Schrodinger's equation (time-independent) where $\frac{d^2ψ}{dx^2}=-2(E-V)ψ$, where I have to consider $V = 0$ at all times. I have been asked to use Python in ...
Entangled Being's user avatar
1 vote
2 answers
190 views

Find the smallest convex hull that enclose an arbitrary point

Given a set of 2D points, I am trying to find the smallest convex hull that encloses an arbitrary point (which, in the general case, is not part of the set). By 'smallest convex hull' I am ideally ...
felipeek's user avatar
  • 121
4 votes
1 answer
90 views

Worst Case complexity of a search engine algorithm

Computer make it possible to find information in large databases. However, the results are often too large to be returned in their entirety to the user who requests them. Computer therefore sort the ...
user avatar
12 votes
2 answers
2k views

How do I find the minimum-area ellipse that encloses a set of points?

I have a set of points that resembles more of an ellipse than a circle. I implemented the optimization formulation below and the solution gives a circle. I tried with various initial values, still to ...
physicsnovice's user avatar
0 votes
1 answer
169 views

Could we train an AI to find (only) Mersenne primes and beat the current record?

Could we train an AI to find only Mersenne primes and beat the current record $2 ^ {82 589 933} - 1$? A Mersenne number is a number of the form $2 ^ n - 1$ (where n is a non-zero natural number), a ...
Extrazlove's user avatar
3 votes
1 answer
276 views

How to interpret if $\displaystyle \sum_{j = 0}^{n} \frac {1}{j!}$ is a stable algorithm for computing $e$?

I am trying to solve problem $15.1$ from Numerical Linear Algebra by Trefethen and Bau, which reads Determine whether the algorithm is backward stable, stable but not backward stable, or unstable. ...
user56202's user avatar
  • 163
2 votes
1 answer
792 views

Why is subtraction a stable operation?

In Numerical Linear Algebra by Trefethen & Bau, it is claimed that subtraction is backward stable. Here is the proof: Let $f(x, y) = x-y$ and let $\tilde f(x,y)$ be the answer you get when doing $...
user56202's user avatar
  • 163
6 votes
1 answer
197 views

General approach to infinite sums

My question is specific to algorithms and models of computation. I would like to write code to evaluate the following expression quickly and accurately: $$\log \left( \sum_{i=1}^{\infty}{I_{\nu+i}(2\...
Lewkrr's user avatar
  • 163
1 vote
0 answers
127 views

Fast evaluation of trigonometric polynomials

Suppose you have a trigonometric polynomial of the form \begin{equation*} x(t) = \sum_{k = 0}^N a_k \cos(2 \pi k f_0 t). \end{equation*} Using Clenshaw algorithm, one can evaluate this polynomial in $...
avril_14th's user avatar
2 votes
0 answers
74 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: ...
albiremo's user avatar
  • 410
1 vote
1 answer
57 views

Resampling an array of objects

Context I have an array of objects (or a list of dictionaries), sorted in order based on a property of each object, say, time. In JSON, it would look something ...
Seth Lutske's user avatar
4 votes
0 answers
508 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 ...
Manuel Oliveira's user avatar
2 votes
1 answer
53 views

Simulate circular mold spread using cellular automata - square emerges instead

I am trying to simulate the spread of mold in a petri dish using a cellular automata based approach. Thanks to the answer in my other question Stochastic cellular automata - algorithm limited by 1 ...
Seth Lutske's user avatar
2 votes
0 answers
34 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. ...
User9124's user avatar
1 vote
0 answers
87 views

What is the limit involving `Sum`, `Subsets`, and `RankedMax` as `t` approaches infinity?

Motivation Suppose we have a countably infinite $A$ with order and group structures and suppose $F_1,F_2,\cdot\cdot\cdot$ are an infinite sequence of finite sets (denoted $\left\{F_n\right\}_{n=1}^{\...
Arbuja's user avatar
  • 53

1
2 3 4 5
12