Questions tagged [algorithms]
A description of the specific steps needed to solve a particular problem in an unambiguous way, expressed in an abstract form.
568
questions
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
1
vote
1
answer
61
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
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
2
votes
1
answer
58
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
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
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}^{\...
- 53
9
votes
1
answer
237
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
104
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
77
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
72
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
92
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
25
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
276
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 ...
- 229
0
votes
1
answer
893
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
111
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
54
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
1k
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
165
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 ...
4
votes
1
answer
836
views
Understand the need for Welford's online algorithm
I am puzzled by the Wikipedia entry discussing many online algorithms for computing the sample variance, including the Welford's online algorithm.
In particular, the sample variance $s_n^2$ can be ...
- 141
1
vote
0
answers
59
views
Largest triangle that contains a point
Given the location of $n$ points on a 2D plane ($P_1, P_2, \ldots, P_n$); and the location of a special point $X$.
Find three points $P_i,P_j,P_k$ ($i \neq j \neq k$) such that point $X$ is inside the ...
0
votes
0
answers
59
views
Storing and retrieving two-dimensional and three-dimensional data
I work on computational geometry.
A huge number of two-dimensional and three-dimensional data are found in my project. Coordinates of polygon and polyhedrons vertices consisted of two-dimensional and ...
- 11
4
votes
3
answers
1k
views
How to determine if 2 rays intersect?
We are given the 2D coordinates of 2 points: the first point is where the ray starts and it goes through the second point. We are given another ray in the same way. How do we determine if they have a ...
- 141
0
votes
0
answers
52
views
Finding block structure of a tensor
Are there any well-known algorithms for partitioning a dense tensor into block-sparse form?
In other words, I need to find a set of non-overlapping blocks that contain all non-zero entries of the ...
- 101
4
votes
2
answers
2k
views
Time Reversibility of Velocity Verlet Algorithm
I'm very new to computational Physics and am finding conflicting statements on whether the velocity Verlet algorithm, defined as:
$\begin{align}
x_{n+1} &= x_n + v_n \Delta t + \frac{1}{2} a_n \...
- 141
1
vote
1
answer
233
views
Asymptotic complexity of fixed-rank SVD
According to the Wikipedia article on Singular Value Decomposition, the asymptotic complexity of computing the SVD of an arbitrary m×n matrix M with m>n by the popular Householder QR methods is O(...
- 131
4
votes
2
answers
135
views
Which algorithms(paper) should be reproduced by a student to enter the field of computational fluid-structure interaction?
We'd better not to reinvent the wheel. But without some programming, one can hardly understand computational fluid-structure interaction. And I would like to know which papers or algorithms should a ...
- 115
1
vote
0
answers
45
views
Bipartite Euclidean Matching simple to implement approximate algorithm
I am looking for a simple to implement algorithm for the bipartite euclidean matching problem (or an implementation of any practical algorithm). I am aware of Agarwal's paper, but I would like to ...
- 1,271
1
vote
1
answer
97
views
An efficient algorithm to find Nearest Neighbours
So imagine I have a $m$ vectors each of dimension $d$. Lets call them, $\vec x_{i}$, with $i = 1, 2, 3, 4, 5, \dots, m$. Now the idea is to find the neighbours of $\vec x_{i}$ (calling them $\vec x_{j}...
- 263
2
votes
3
answers
1k
views
On the reordering of sparse matrices
I have been reading on different techniques used to reorder sparse matrices to achieve better performance, the most popular being the Cuthill-McKee or Reverse Cuthill-McKee algorithm. Most of those ...
- 337
2
votes
0
answers
333
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
7
votes
1
answer
1k
views
Cheap recalculation of eigenvalues and eigenvectors for a low-rank update of the matrix
Suppose I have a correlation matrix, $A$, and I already have the eigenvalues and eigenvectors of this matrix.
For a given vector, $\mathbf{\mathit{v}}$, I want to calculate the eigenvalues and ...
- 189
0
votes
0
answers
154
views
Producing Voronoi diagram in three dimensional
A Voronoi diagram is a kind of tesselation that divided the medium into polygons in 2D and polyhedrons in 3D.
Although there are many algorithms to construct a Voronoi diagram, some of them are faster ...
- 11
3
votes
3
answers
582
views
What are some algorithms to calculate the width of an arbitrary polygon when a bounding box approximation is inaccurate
What are some alternative algorithms to creating a bounding box for finding the max width of a concave, simple winding polygon, like the one in the below image? I prefer solutions that are more ...
- 131
0
votes
0
answers
84
views
Derivative-free ill-conditioned non-linear least squares
I am looking for a package which can solve (non-linear) least squares problems without the use of derivatives (because of an expensive model), but which also deals with ill-conditioning well (such as ...
- 131
0
votes
0
answers
317
views
Explanation of Givens rotation in Jacobi Rotation SVD
I'm trying to implement Singular Value Decomposition (homework of sorts) via the Jacobi Rotation method (more info here, pages 11 and 12).
I am stuck at the bullet saying (sorry for the picture, but I'...
- 101
2
votes
1
answer
55
views
How do you construct a self-similar binary structured-tree?
Please excuse me if this question somehow looks trivial or not really interesting, but I recently have a hard time to convince someone else that my algorithm for constructing a self-similar binary ...
- 2,332
0
votes
0
answers
242
views
Surface mesh from labeled 3D points
I'm trying to figure out how to create a surface mesh from a set of labeled 3D points. The 3D object could be something like part of a cave system or asteroid where there would be parts of the surface ...
1
vote
0
answers
36
views
Combining many probabilities, modifying, seeking general formula
CONTEXT
I need to combine the probability of occurrence of many thousands of events for millions of individuals (trees) in an agent-based/individual-based simulation model developed in NetLogo (agent-...
- 11
2
votes
1
answer
147
views
Question regarding the energy computation of the Ising-Spin Model
In most of the Monte-Carlo-Algorithms I studied, I found, at the place where they compute the energy, always a line of code, where they divided by four.
For example, this code-snippet is taken from ...
- 23
2
votes
1
answer
137
views
Machine Learning for Optimization
I have a function which takes 100+ coefficients and outputs $x$. I wish to optimise $x$.
Running the simulation 50 000 times will take around 15 minutes, however, this happens in parallel - and the ...
- 123
1
vote
0
answers
58
views
Assume $AX = C$. How to determine which entry of $BX - D$ is non-negative?
Let $A,B$ be $n \times n$ matrices and $C,D$ be $n \times 1$ matrices. Moreover, all entries of $A,B,C,D$ are non-negative. Assume that there is a unique matrix $X$ that solves $AX = C$.
My goal is ...
- 207
0
votes
2
answers
498
views
Best way to find biggest & smallest number in a random list?
Given a list of some length, containing random numbers.
What method would need the least amount of checks to find the largest & smallest number in the list?
My best guess is: (list_length)/2 ...
- 101
-1
votes
1
answer
33
views
An almost surly fine-time game of coin toss where you win with probability $p$
Given a fair coin and a number $p\in(0,1)$. How do you design a game that finishes in a finite number of tosses with a probability of $1$? And further, with the probability $p$ you win the game.
I ...
- 99
1
vote
1
answer
86
views
Newman algorithm yielding different result to what is given in his paper
Summary
I am trying to implement Newman's algorithm for community detection, outlined in this paper. I am testing my implementation against one of the datasets used in that paper to benchmark the ...
- 31
2
votes
2
answers
122
views
Using MILP to place a set of primers along a genome
Define variables $p_i,u_i\in\{0,1\}^G$, for $i=1,\ldots,8$ and $G=30000$.
Let $v$ be a constant vector also in $\{0,1\}^G$, with approximately 25% of its entries equal to $1$ (randomly located).
Let ...
- 461
1
vote
0
answers
28
views
Unable to achieve semi-linear running time in computation of continuant
I am trying to compute the continuant of a list of numbers $a_0, a_1,...,a_n$, defined by the recursion relation: $K_{n+1} = a_{n+1} K_n + K_{n-1}$ and $K_0 = 1$ (see Wikipedia).
I am trying to use ...
- 51
4
votes
1
answer
108
views
Can you compare integer part of two fractions without division?
Suppose we need to compare
$\left \lfloor{a / b}\right \rfloor $
and
$\left \lfloor{c / d}\right \rfloor $
.
One way would of course be to calculate $a/b$ and $c/d$ by division. Is their a faster way?
- 51
5
votes
2
answers
1k
views
Fast algorithm for computing the similarity between two arrays
Suppose there are two arrays (They have the same length), I want to give a quantitative description about the similarity between them. I define a formula like this, which means we can shuffle them ...
- 53
5
votes
1
answer
207
views
Is there an efficient algorithm for calculation of continued fraction expansion from decimal digits?
Suppose to calculate the continued fraction expansion of $\pi$, the common-sense algorithm would be to take the decimal part, perform inversion, which will give the next term as integer part, and the ...
- 51
7
votes
1
answer
246
views
Numerically stable and fast sum of last K elements in sequence
Suppose I have a long, possibly infinite, sequence $x := [x_1, x_2, ...]$, and I want to use it to compute another sequence $y:=[y_1, y_2, ...]$ where each element is the sum of the last K elements of ...
- 171