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
votes
0answers
31 views

Integer $u$ is known to divide integer $v$. Division algorithms for computing $v÷u$?

Integer $u$ is known to divide integer $v$. Division algorithms for computing $v÷u$? Let $0 \lt u \lt v$ are numbers such that $u \mid v$. Are there algorithms (computer technology) that can use this ...
1
vote
1answer
36 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(...
2
votes
1answer
46 views

How to select initial time step in adaptive time step ODE solver (TR-BDF2)

The Problem I am currently reconstructing a TR-BDF2 scheme which contains the following two stages: \begin{align} y_{n+\gamma} & = y_n + \gamma \frac{h}{2}\left( f_n + f_{n+\gamma} \right) \...
4
votes
1answer
83 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
28 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
58 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
203 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
76 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 ...
5
votes
1answer
425 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
25 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
102 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
69 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
48 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
38 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 ...
0
votes
0answers
20 views

Hawkes Process : recursive formula for : $R'_{m,n} (k) = \sum_{ \{i : t_i^n < t_k^m \} } (t_k^m - t_i^n) \exp ( - \beta_{m,n} ( t_k^m - t_i^n ) ) $

Following the advice of a fellow mathematician, I am asking my question here from (https://mathoverflow.net/questions/365554/hawkes-process-recursive-formula-for-r-m-n-k-sum-i-t-in-t) I need to use a ...
0
votes
0answers
44 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
0answers
22 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-...
2
votes
1answer
42 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 ...
1
vote
1answer
98 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 ...
1
vote
0answers
51 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 ...
0
votes
2answers
67 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 ...
-1
votes
1answer
28 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 ...
0
votes
0answers
35 views

What constraints, if any, are there on constructible patterns in Conway's Game of Life?

Conway's Game of Life is Turing-complete. Interesting demos of this: A clock Tetris I note that Turing-completeness doesn't require that any specifically encoded state be reachable, does it? ...
1
vote
1answer
53 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 ...
2
votes
2answers
99 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 ...
1
vote
0answers
25 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 ...
0
votes
0answers
29 views

Boundary conditions for triangular lattice in comsol

I am trying to simulate an infinite 2D triangular lattice in Comsol but I am confused that how should I use periodic floquet boundary conditions on the unit-cell. A unit cell that I am using is given ...
3
votes
1answer
85 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?
5
votes
2answers
149 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 ...
5
votes
1answer
65 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 ...
7
votes
1answer
130 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 ...
5
votes
0answers
76 views

Efficient way to find eigenvalues of complex symmetric matrix with real off-diagonal elements

My goal is to find all eigenvalues (and eigenvectors) in a given range of magnitudes of a complex symmetric matrix with real off-diagonal elements (only diagonal elements are complex). Currently I'm ...
2
votes
0answers
30 views

Alternatives to breadth-first-search in 3D grid cluster detection?

I've got a question about a good way to find the quickest algorithm for my problem: problem: I've got a 3D cubical grid containing voxels that are either 1 or 0. It is stored as a flattened array. If ...
2
votes
0answers
40 views

Evaluating integral $F(r_2) = \frac{1}{r_2^n} \int_0^{r_2} r_1^n f(r_1)\ \mathrm{d}r_1$ without growing instability

I have the following expression to be numerically integrated in a vector-based library (e.g. numpy, MATLAB, etc), $$ F(r_2) = \frac{1}{r_2^n} \int_0^{r_2} r_1^n f(r_1)\ \mathrm{d}r_1, $$ where $n$ is ...
1
vote
0answers
18 views

SHREC 2010 Descriptors

I will appreciate if I may find someone how can clarify for me the part regarding the quality of feature descriptor, shown in the figure below: and this screenshot is from the article: SHREC All my ...
3
votes
1answer
77 views

Evaluate 3D Shape Descriptor

I'm trying to create my own 3d shape descriptor, the idea is that how I may evaluate how much my descriptor is well and good? What I checked is that they evaluate descriptors through shape matching, ...
3
votes
0answers
68 views

Computation of Troullier-Martins pseudowavefunctions

The computation of Troullier-Martins pseudowavefunctions has been described in [1]. The pseudowavefunction $R^{\textrm{PP}}_l$ is defined by $$ R^{\textrm{PP}}_l(r) = \left\{ \begin{array}{ll} R^{\...
10
votes
3answers
344 views

Should benchmarkings be done at all? What is the point?

I am reading a paper which compares algorithm A versus algorithm B. It shows that algorithm A is faster than algorithm B via benchmarking that shows the CPU time. What is the point of this? Any ...
1
vote
0answers
70 views

How to approach geographic data interpolation by distance?

let's say I have a set of geographic locations (lat, lng) resulting from a query. Those locations have some kind of internal ranking, my set is sorted by this number in a descending order. Now I'm ...
3
votes
1answer
93 views

Calculate Transformation Matrix between two sensors

My question is if I can calculate the transformation matrix between two sensors. Each sensor provides a $4\times 4$ matrix for every timestep recorded. The sensors are moving and have some noise in ...
0
votes
1answer
90 views

What is Voronoi particle tracking?

I've been trying to track this down, but google is giving paywall papers that don't appear to be directly related to computational science, or simply don't explain the source algorithm. There's an ...
6
votes
1answer
326 views

Understanding butcher tableau when it comes to implicit methods

I've been learning about butcher tables and am having some difficulty understanding how to translate them when it comes to implicit methods. Specifically, I'm looking at backwards Euler: \begin{array}...
2
votes
0answers
157 views

What exactly is the cause(s) of blow-up for too-large step size in a method like RK4?

I have been working on creating a few home-made numerical methods, and I am using them to visualize text-book problems from my Strogatz dynamics textbook. It feels like a good way to learn numerical ...
1
vote
0answers
63 views

Hybrid Ellpack-Itpack (ELL) + COO Sparse Matrix Representation decomposition threshold

Hybrid ELL-COO sparse matrix representation can be done as in the picture, I was looking intensively, however I couldn't find out what is the threshold of decomposing the original matrix into ELL part ...
3
votes
1answer
87 views

Efficient computation of leading eigenvector of a matrix product of the form $ADA^T$, where $D$ is diagonal

Let $A=[A_1|\ldots|A_m] \in \mathbb R^{n \times m}$ with $n \gg m \gg 1$ and $D=\text{diag}(d_1,\ldots,d_m)$ where $d_1,\ldots,d_m > 0$, and consider the $n\times n$ positive-definite matrix $X=\...
1
vote
1answer
219 views

Weighted moving variance

i have a time-series and, in analogy with exponentially weighted moving average, i would like to compute the exponentially weighted moving standard deviation or variance in an efficient, numerically ...
0
votes
1answer
81 views

Dealing neighbor list in NVT Monte Carlo (MC) simulation

I'm making a NVT Monte Carlo (MC) simulation code with only short range interaction. I found many MC tutorial codes (usually Lennard-Jones system) in online. However, most of them are doing energy ...
4
votes
2answers
164 views

Efficient algorithm to decide if a graph is a cactus?

A cactus is a connected graph in which every edge belongs to at most one simple cycle. How should one modify the Depth First Search algorithm to obtain an efficient algorithm that determines if a ...
5
votes
1answer
305 views

Fast algorithm for computing cofactor matrix

I wonder if there is a fast algorithm, say ($\mathcal O(n^3)$) for computing the cofactor matrix (or conjugate matrix) of an $N\times N$ square matrix. And yes, one could first compute its determinant ...
1
vote
1answer
37 views

How is the D value being updated at simple RRT algorithm?

I am studying the following lecture (image) regarding 5 iterations of the simple RRT algorithm. I am trying to understand how each value is being updated regarding each iteration. I have figured out ...

1
2 3 4 5
11