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
3 votes
0 answers
33 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 ...
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 ...
user avatar
2 votes
1 answer
91 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 ...
user avatar
  • 195
0 votes
0 answers
49 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 ...
user avatar
0 votes
0 answers
37 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 ...
user avatar
3 votes
1 answer
106 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 ...
user avatar
  • 133
2 votes
1 answer
94 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 ...
user avatar
  • 123
0 votes
2 answers
98 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 ...
user avatar
2 votes
0 answers
42 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 ...
user avatar
-1 votes
1 answer
22 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: ...
user avatar
0 votes
1 answer
163 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$ ...
user avatar
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 $...
user avatar
  • 119
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. ...
user avatar
  • 123
1 vote
1 answer
43 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, ...
user avatar
  • 852
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 ...
user avatar
2 votes
1 answer
52 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 ...
user avatar
1 vote
1 answer
185 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 ...
user avatar
1 vote
2 answers
126 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 ...
user avatar
  • 121
4 votes
1 answer
83 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
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 ...
user avatar
0 votes
1 answer
160 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 ...
user avatar
3 votes
1 answer
178 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. ...
user avatar
  • 163
2 votes
1 answer
711 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 $...
user avatar
  • 163
6 votes
1 answer
159 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\...
user avatar
  • 163
1 vote
0 answers
117 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 $...
user avatar
2 votes
0 answers
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: ...
user avatar
  • 382
1 vote
1 answer
52 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 ...
user avatar
3 votes
0 answers
260 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 ...
user avatar
2 votes
1 answer
43 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 ...
user avatar
2 votes
0 answers
27 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. ...
user avatar
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}^{\...
user avatar
  • 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=...
user avatar
  • 53
4 votes
1 answer
77 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 ...
user avatar
2 votes
1 answer
73 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 ...
user avatar
0 votes
1 answer
70 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 ...
user avatar
0 votes
1 answer
81 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?
user avatar
  • 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 "...
user avatar
  • 109
4 votes
3 answers
201 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 ...
user avatar
  • 195
0 votes
1 answer
462 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 ...
user avatar
  • 123
3 votes
1 answer
88 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 ...
user avatar
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 ...
user avatar
  • 111
4 votes
1 answer
303 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:...
user avatar
  • 145
5 votes
2 answers
142 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 ...
user avatar
4 votes
1 answer
432 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 ...
user avatar
  • 141
1 vote
0 answers
38 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 ...
user avatar
0 votes
0 answers
50 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 ...
user avatar
  • 11
4 votes
3 answers
526 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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
4 votes
2 answers
900 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 \...
user avatar
  • 141
1 vote
1 answer
111 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(...
user avatar
  • 131

1
2 3 4 5
11