Questions tagged [algorithms]
A description of the specific steps needed to solve a particular problem in an unambiguous way, expressed in an abstract form.
489
questions
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
36 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
74 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
49 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
63 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
25 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
47 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 ...
1
vote
2answers
91 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
16 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
84 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
140 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
54 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
117 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
73 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
24 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
66 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
65 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
339 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
67 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
75 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
57 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
236 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
58 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
81 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
31 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} \...
1
vote
1answer
119 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
63 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
127 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 ...
4
votes
1answer
191 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
35 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
33 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 ...
0
votes
1answer
230 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
45 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 ...
3
votes
1answer
111 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, ...
3
votes
1answer
95 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
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 ...
0
votes
1answer
134 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 ...
2
votes
3answers
164 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 ...
1
vote
0answers
44 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
76 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 ...
0
votes
1answer
76 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 ...
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 ...
0
votes
1answer
20 views
Binary tree for 2 elements [closed]
I want to understand Binary Search for 2 element list made of 1,2. I draw a tree as below. Is it correct?
If I want to search for an element 2, it will make 2 comparisons. If I want to search for ...
3
votes
1answer
63 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 ...
