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
1
vote
1answer
51 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. ...
1
vote
1answer
36 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, ...
2
votes
0answers
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 ...
2
votes
1answer
51 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
1answer
146 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 ...
1
vote
2answers
105 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 ...
4
votes
1answer
80 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 ...
12
votes
2answers
1k 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 ...
0
votes
1answer
150 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 ...
2
votes
1answer
153 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. ...
1
vote
1answer
695 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 $...
6
votes
1answer
149 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\...
1
vote
0answers
110 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 $...
2
votes
0answers
66 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: ...
1
vote
1answer
50 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 ...
3
votes
0answers
107 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 ...
2
votes
1answer
40 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 ...
2
votes
0answers
26 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. ...
1
vote
0answers
83 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}^{\...
9
votes
1answer
220 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=...
4
votes
1answer
72 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 ...
2
votes
1answer
72 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 ...
0
votes
1answer
69 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 ...
0
votes
1answer
79 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?
0
votes
0answers
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 "...
1
vote
0answers
53 views

Ising model in Python (Magnetization Scaling)

I am trying to implement the Ising Model in Python for Gibbs Distribution: $$\pi(x) = \frac{1}{Z(\beta)} e^{-\beta H(x)}$$ \begin{align*} p(x,y)&=r(x,y) \cdot \min \left( \frac{\pi(y)}{\pi(x)},1 \...
4
votes
3answers
185 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 ...
0
votes
1answer
239 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 ...
3
votes
1answer
83 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 ...
0
votes
2answers
49 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 ...
4
votes
1answer
126 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:...
5
votes
2answers
134 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 ...
3
votes
1answer
305 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 ...
1
vote
0answers
37 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
0answers
48 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 ...
3
votes
3answers
326 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 ...
0
votes
0answers
51 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 ...
4
votes
2answers
705 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 \...
1
vote
1answer
90 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(...
4
votes
2answers
124 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 ...
1
vote
0answers
31 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
vote
1answer
70 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}...
2
votes
3answers
522 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 ...
2
votes
0answers
146 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 ...
6
votes
1answer
803 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 ...
0
votes
0answers
55 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 ...
3
votes
3answers
287 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 ...
0
votes
0answers
78 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 ...
0
votes
0answers
118 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'...
2
votes
1answer
48 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 ...

1
2 3 4 5
11