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
26 views

Code for computing the Partial Fréchet Distance [closed]

I am looking for a code (Python, Matlab, R) to compute the partial Frechet distance. That is a similarity measure for curves that takes into account partial matchings. References Buchin, K., Buchin,...
2
votes
0answers
31 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 ...
0
votes
1answer
187 views

Chip testing problem

An engineer has n supposedly identical integrated-circuit chips that in principle are capable of testing each other. The engineer test jig accommodates two chips at a time. When the jig is loaded, ...
4
votes
1answer
141 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 ...
0
votes
1answer
46 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 ...
1
vote
0answers
15 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
53 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, ...
6
votes
1answer
161 views

Accurate and efficient computation of the inverse Langevin function

The Langevin function $\mathcal{L}(x) = \mathrm{coth}(x) - \frac{1}{x}$ occurs in computations related to elastomers and paramagnetic materials. It is easily computed accurately and with high ...
2
votes
1answer
79 views

How to find a pair of divisors as close as possible to each other?

For a given integer $n\in\mathbb{N}^*$, I want to find a pair $(x,y)\in{\mathbb{N}^*}^2$ such that $x*y=n$ and $|y-x|$ is as small as possible. A naive algorithm I found is : ...
2
votes
3answers
147 views

Clustering with points lying along different 3D planes

I have a bunch of data points in 3D that lie along a few planes. What would be the best approaches to estimate the normals of these planes? Edit: There are roughly equal number of points lying along ...
3
votes
0answers
62 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
333 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 ...
2
votes
0answers
28 views

Piecewise-linear Continuations vs Marching Squares/Cubes

It seems that both piecewise-linear continuation and marching squares are methods to produce iso-contours of a scalar function given the function's values on a grid. It seems that piecwise-linear ...
1
vote
0answers
66 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
67 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
0answers
40 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 ...
5
votes
1answer
192 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
46 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
71 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=\...
0
votes
0answers
29 views

solving electron motion in undulator by Boris method

I am trying to use Boris scheme to solve the electron trajectory in undulator. The undulator field I used is: $$B_x = b_0\sin(2\pi \tfrac{z}{\lambda_u})$$ where $b_0 = \dfrac{2\pi c_{0}K}{q m_{e} \...
22
votes
10answers
6k views

Which algorithm is more accurate for computing the sum of a sorted array of numbers?

Given is an increasing finite sequence of positive numbers $z_{1} ,z_{2},.....z_{n}$. Which of the following two algorithms is better for computing the sum of the numbers? ...
1
vote
1answer
54 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 ...
25
votes
6answers
4k views

How can the gravitational n-body problem be solved in parallel?

How can the gravitational n-body problem be solved numerically in parallel? Is precision-complexity tradeoff possible? How does precision influence the quality of the model?
11
votes
3answers
2k views

Volume of 3D convex hull of small point sets all on the hull

I have a question that is similar to this one asked before except in 3D, and I only need the volume, not the actual shape of the hull. More precisely, I'm given a small set of points (say, 10-15) in ...
4
votes
2answers
118 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 ...
1
vote
3answers
836 views

Algorithm to compute the intersection of two lines given their cartesian equations

I'm looking for a way to compute the coordinates of the intersection of two lines. Each lines are defined with a point and a normal vector. We can assume than the normal vectors are not zero and ...
1
vote
1answer
30 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 ...
0
votes
0answers
31 views

A preconditioner for self-consistent iteration

I tried to derive a preconditioner for self-consistent iteration similar to section IX in arXiv:0804.2583. For simplicity, consider here only one orbital (one or two electrons) systems. Suppose that ...
8
votes
2answers
12k views

The easiest way to find intersection of two intervals

Right now I stuck with a problem. It seems to be really trivial one, but still it is hard for me to find an appropriate solution. The problem is: One has two intervals and are to find the intersection ...
6
votes
1answer
411 views

Fast algorithm for computing matrix square root using randomized linear algebra?

Is there a fast algorithm for computing the matrix square root of a real symmetric matrix using random matrices or randomized algorithms?
5
votes
4answers
3k views

Simulated Annealing proof of convergence

I implemented downhill simplex simulated annealing algorithm. Algorithm is very hard to tune, w.r.t. parameters including cooling schedule, starting temperature... My first question is about ...
2
votes
1answer
131 views

What is the name of the optimization algorithm that uses random sampling?

I am generating random weight as per e.g. below. The I generate a set of 3 values say 100, 250, 300 and I multiple them with the weights below Initial population. ...
0
votes
1answer
406 views

Drunken Man in Matlab

I wrote a script that plots the results of the "drunken lamppost" problem in MATLAB. Now I need to create a road-width from -3 to +3, length from 0 to infinity but the drunk can walk just ahead. It ...
19
votes
4answers
4k views

Is Fortuna or Mersenne Twister preferable as an algorithmic RNG?

A recent answer mentioned the use of Fortuna or Mersenne Twister Random Number Generators (RNGs) to seed a Monte Carlo simulation. I hadn't heard of Fortuna before so I looked it up - looks like it is ...
7
votes
2answers
759 views

Bin-packing: Maximise number of bins / “Fukubukuro” problem?

I recently encountered a problem that looks like a variation of bin packing or knapsack problem, but with the objective to maximise the number of bins/knapsacks: Consider there is a list of M items ...
7
votes
4answers
253 views

Testing for stability of a simulated dynamical system

Background and question I often work with simulations of dynamical systems and I usually track a single parameter $x$, such as the number of agents (for agents based models) or the error rate (for ...
1
vote
3answers
258 views

Traveling Salesman Problem

First off some context. The Traveling Salesman Problem(TSP) is to find the most efficient route passing through a series of points only once. However, there is no perfect function to solve for this in ...
0
votes
1answer
123 views

Finding a shortest path in a graph

If each edge of a graph $G$ is unweighted or has equal weights, then the shortest path between two nodes in that graph is the path that contains the fewest number of edges. Such a path can be obtained ...
1
vote
0answers
74 views

Find a vector B that minimizes |W-A*B|

I want to find a candidate vector $B$ that $$\min|(W - A_i * B_i)|$$ $$ a_i > 0,\ A_i=\{a_0,...,a_i\},\ B_i=\{-1,0,1\}^i$$ For example, given $$W = 0.6,\quad A_4 = [0.1, 0.2, 0.4, 0.7] $$ one ...
4
votes
1answer
43 views

Single-variable multimodal derivative-free optimization (for a well-behaved function)

Are there well-established approaches to single-variable multimodal optimization? Given $f:\mathbb{R}\rightarrow\mathbb{R}$ that: has several local minima within a given range of interest $[a,b]$ is ...
2
votes
1answer
73 views

How to justify using available code (in different language) for comparing algorithms

I have proposed an algorithm for a scheduling problem in a submitting paper. In the revision, the reviewer asked us to compare with another algorithm from the literature. Our algorithm is in MATLAB, ...
7
votes
1answer
140 views

Element-wise thresholding a low-rank matrix in O(n) time?

Define the element-wise thresholding operator $T_\tau(\cdot)$ with threshold $\tau$ as $$ [T_\tau(X)]_{i,j} = \begin{cases} X_{i,j} &\mbox{if } |X_{i,j}| \ge \tau, \\ 0 & \mbox{if } |X_{i,j}|...
0
votes
1answer
75 views

Stability of PDEs

I am currently trying to solve some PDEs with FiPy. At page 56, the manual mentions (https://www.ctcms.nist.gov/fipy/download/fipy-3.0.pdf). The largest stable timestep that can be taken for this ...
2
votes
0answers
47 views

Cover a polygon with least amount of parallelograms [closed]

I am solving the task that is as follows: Input: a polygon. Can be any kind of polygon without self intersections. Can be a non-convex and with holes inside. Goal: to cover it with 2 (at least) or ...
1
vote
0answers
37 views

How to numerically calculate the transition dipole integral in periodic systems?

Now I have wave functions $\psi_a$ and $\psi_b$ of two states in Gaussian CUBE format. I'd like to evaluate the transition dipole moment integral $\pmb\mu$ between these two states. As my simulation ...
0
votes
1answer
74 views

Python sequence cluster exercise

I am working through an exercise in my textbook and implementing the code in Python to practice dynamic programming. I feel like I am right on the edge of figuring it out, but after many hours, I come ...
1
vote
0answers
35 views

Number of $S_n$-orbits in $P^k(\{1,\dots,n\})$

This is a particular case of a question I asked on Mathematics Stackexchange, question which got no answer so far. Let $n$ and $k$ be integers with $n\ge1$, $k\ge0$, and let $a(n,k)$ be the number of ...
6
votes
1answer
265 views

Eigenvector with maximum overlap

Given a matrix $M$ and a vector $v$, is there an efficient method to find the normalized eigenvector of $M$ that is closest to $v$, in that it has maximal overlap. More explicitly, a vector $v$ can be ...
3
votes
1answer
59 views

Radiation heat transfer between surfaces

I'm trying to model the temperature distribution over a curved surface. Apart from the heat equation, I need to take into account the energy emission/absorption through electromagnetic radiation. The ...

1 2 3 4 5 10