Questions tagged [algorithms]
A description of the specific steps needed to solve a particular problem in an unambiguous way, expressed in an abstract form.
550
questions
2
votes
1
answer
59
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
...
- 121
1
vote
1
answer
53
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
0
answers
30
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
0
answers
62
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 ...
- 11
11
votes
5
answers
8k
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 ...
- 143
1
vote
1
answer
70
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
-1
votes
1
answer
60
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 :
...
- 143
3
votes
0
answers
36
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
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 ...
2
votes
1
answer
222
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 ...
- 195
0
votes
0
answers
52
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 ...
0
votes
0
answers
39
views
Solving Symmetric/Hollow Matrix issue
I have a particular issue and need something creative or solution from calculus.
I have Symmetric/Hollow Matrix, a numbers are % of mismatch between them. Ideally, all of them should be 0, but I have ...
- 101
3
votes
1
answer
130
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
2
votes
1
answer
98
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
0
votes
2
answers
193
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 ...
2
votes
0
answers
50
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
-1
votes
1
answer
24
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: ...
0
votes
1
answer
312
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$ ...
- 11
1
vote
0
answers
72
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 $...
- 219
1
vote
1
answer
75
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. ...
- 123
1
vote
1
answer
49
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, ...
- 944
2
votes
0
answers
35
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
1
answer
158
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 ...
1
vote
1
answer
206
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 ...
- 13
1
vote
2
answers
151
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 ...
- 121
4
votes
1
answer
86
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 ...
user41897
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 ...
- 123
0
votes
1
answer
164
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 ...
- 11
3
votes
1
answer
260
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.
...
- 163
2
votes
1
answer
745
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 $...
- 163
6
votes
1
answer
172
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\...
- 163
1
vote
0
answers
120
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 $...
- 111
2
votes
0
answers
69
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
1
vote
1
answer
54
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 ...
- 197
4
votes
0
answers
384
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 ...
- 191
2
votes
1
answer
48
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 ...
- 197
2
votes
0
answers
28
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
1
vote
0
answers
86
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}^{\...
- 53
9
votes
1
answer
226
views
Is there a way we can compute my sum involving `subsets` more efficiently?
Suppose we have a countably infinite $A$ and $F_1,F_2,\cdot\cdot\cdot$ are an infinite sequence of finite sets (denoted $\left\{F_n\right\}_{n=1}^{\infty}$) such that $\bigcup\limits_{n=1}^{\infty}F_n=...
- 53
4
votes
1
answer
96
views
Stochastic cellular automata - algorithm limited by 1 cell per timestep
Context
Let's say I am trying to model the spread of mold in a petri dish, using a stochastic cellular automata approach. The petri dish can be thought of as a grid of 1mm x 1mm squares, each called ...
- 197
2
votes
1
answer
74
views
Dividing a continuous domain into small squares; how to perform storage and querying?
I recently had a software engineering interview and was asked a series of questions that was a bit outside of knowledge realm, and I feel like there's some scientific computing principles here (I took ...
- 143
0
votes
1
answer
71
views
Looking for Partinioning Algorithms allowing for Constraints
What algorithms exist that partition the domain according to a black box evaluation function (possibly subject to some assumptions)?
Examples
Simple Example
To better exaplain we consider as our ...
- 11
0
votes
1
answer
83
views
In Lanczos algorithm, can we choose the staring vector to be the first eigenvector of the input matrix A?
In Lanczos algorithm, can we choose the staring vector $v$ to be the first eigenvector of the input matrix $A$? How can we select it? and why $v$ need to have norm 1?
- 1
0
votes
0
answers
24
views
Do the class of Construction Heuristic that does or does not change previous decisions have a name?
I'm writing a paper where I am discussing different types of construction heuristics.
One type does not change previous decisions when adding new elements to the solution. I'd call them "...
- 109
4
votes
3
answers
211
views
Algorithms to generate spherical codes
A spherical code, specified by the parameters $(n,N,t)$, is a set of $N$ coordinates on the $n$-dimensional unit hypersphere such that the set of dot products between any two unit vectors from the ...
- 195
0
votes
1
answer
597
views
Trouble Implementing 1d Wave Equation Finite Difference Solver
Im trying to solve the 1d Wave Equation on $x \in \mathbb{R}, t > 0$: $$u_{tt} = c^2u_{xx}, \hspace{5mm} u(x,0) = \cos(4 \pi x), \hspace{5mm} u_t(x,0) = 0$$ with $c = 1$ and a periodic boundary ...
- 123
3
votes
1
answer
92
views
Maintain unitary time evolution for a nonlinear ODE
I want to solve a nonlinear ODE of matrix $A(t)$
$$\mathrm{i}\dot A = A(t)M(t),\:\mathrm{with}\: M(t)=A^\dagger(t)H(t)A(t)$$ where $H(t)$ and hence $M(t)$ are Hermitian. Therefore, I presume the time ...
- 303
0
votes
2
answers
50
views
Technique or Pattern to calculate conditional statement
I am attempting to create a conditional statement that compares four (4) true/false conditions. Depending on the state of these four conditions (either true or false) the conditional statement will ...
- 111
5
votes
1
answer
603
views
Algorithm to merge two polygons (using connectivities)?
I am struggling with implementing an algorithm that does one simple thing:
Consider two polygons (one can just draw any two polygons and number their vertices), whose connectivities in a node list are:...
- 155
5
votes
2
answers
149
views
Exponent log to compute reciprocal power?
A MATLAB library seems to overcomplicate a computation:
exp( (log(a) - log(b))/b )
which is mathematically equivalent (assuming real & positive ...
