Questions tagged [data-structures]
For questions about data structures (e.g. arrays, lists, queues, dictionaries) and how to best use them in a computational setting.
31
questions
1
vote
2
answers
350
views
Robust alternative to HDF5 for storing large datasets
When running my simulations I usually get result files with typical sizes of 10 GByte and larger. They contain vectors and matrices with data type float, double, complex float and complex double.
...
- 543
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 ...
- 143
0
votes
1
answer
128
views
Mesh aspect ratio issue with adaptive mesh refinement (AMR)
I am working on implementation of AMR for my finite volume code. Let me use a 2-D mesh to describe my question.
Starting with SINGLE initial cell (let the mesh refine level k = 0) as a root of a quad-...
- 31
1
vote
1
answer
82
views
k nearest neighbors dictionary for vectors?
Does there exists a data structure with these properties
Stores vectors in a dictionary
When given a key that is also a vector, returns the k nearest vectors using a similarity metric (e.g. Euclidean,...
- 111
1
vote
2
answers
323
views
Why OpenFOAM uses its own data structures and linear solvers?
I wonder why OpenFOAM code has its own data structures Lists, HashTables, ... etc. when there is the STL in C++?
Another ...
2
votes
2
answers
441
views
Visualization of Quad/Octree data Structures
I have a simple C++ quadtree implementation. The implementation subdivides node into four children as if there is more than one point in that particular node. At the moment I want to visualize how ...
- 41
0
votes
0
answers
27
views
Direct and Inverse efficient mapping of 3D cartesian positions in a 1D array
I saved a sample of $N$ Cartesian locations $\{x_i, y_j, z_k\}$ inside a one-dimensional array $\mathbf{a} = \{a_l\}_{l = 1}^N$.
How can I access back (efficiently) the $l$-location of the array $\...
- 129
1
vote
0
answers
118
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 ...
- 113
2
votes
1
answer
83
views
Why should one use a tree structure to represent discrete function spaces?
In FEM/FV codebases, I stumbled upon the fact that the discretized functionspaces are represented within the code as a tree structure. I find this very puzzling.
Example: lets say somebody wants to ...
- 2,111
1
vote
1
answer
908
views
How to generate a face list from vertices?
I have a little background in writing toy finite volume CFD codes. In 2D Cartesian scenarios, I typically take $x_{\min}$, $x_{\max}$, $y_{\min}$, $y_{\max}$, and the number of points in $x$ and $y$ ...
- 67
8
votes
1
answer
441
views
bit-packing and compression of data structures in scientific computing
I recently came across this paper, which describes a scheme for saving memory in representing sparse matrices. A 32-bit integer can store numbers up to ~4 billion. But when you solve a PDE you've gone ...
- 8,172
2
votes
1
answer
120
views
Union of closed intervals on $\mathbb{R}$
Suppose there are multiple intervals on $\mathbb{R}$, e.g., $[0,0.5]$, $[0.4,1]$, $[1.5,2]$, the union of them should be $[0,1]$ and $[1.5,2]$. Is there a specific datastructure (or algorithm) for ...
- 121
0
votes
1
answer
55
views
Which data structure contains of one parent node and many child nodes [closed]
I like to represent the following numbers in a data structure, like in trees or list but with one parent node and possibly many child nodes
1.3.1.1.0
1.3.1.1.1
1.3.1.1.2
1.3.1.2.0
1.3.1.2.1
1.3.1.3.0
...
- 3
2
votes
2
answers
64
views
Efficient Representation of (spatially sparse) spatial time series
Background
I have a huge dataset consisting of points (on a plane) together with a timestamp for each point. This is a collection of car GPS measures, giving us the location (latitude/longitude) of ...
- 23
1
vote
1
answer
136
views
How to handle 2D and 3D models efficiently
My coworkers and I have developed a c++ library implementing a "3D Geological Model" class. Goal of this library is to provide a data structure that is used in computational codes (such as Finite ...
4
votes
0
answers
345
views
Algorithm for face based data-structure - CFD
Good morning
I'm trying to develop an unstructured CFD code to solve Euler equations in a finite-volume (cell-centered) context (learning purposes). I was able to build from a cgns file some basic ...
- 77
2
votes
0
answers
77
views
Data format for Cartesian mesh with cut cells
Is there a mesh data format which is particularly well suited for Cartesian meshes with Dey-Mittra style cut-cells? Ideally, one which does not require converting the cut-cells into a more general ...
- 21
8
votes
2
answers
9k
views
Programming Finite Element Methods in C++
I am trying to develop a library for finite element methods in C++ and for that I am looking at the data structures for meshes. Based on what I've read up on fenics and deal.ii, the general ...
- 322
4
votes
3
answers
227
views
K-nearest neighbours search in subspaces of a high-dimensional space
I'm looking for a good way to partition a large, fairly high-dimensional dataset in order to perform fast kNN searches not just in the full $N$-dimensional space, but also in lower-dimensional ...
- 237
3
votes
5
answers
2k
views
Algorithm for efficient weighted sampling from a collection that can efficiently be updated
I'm writing a Monte Carlo simulation in which I have to maintain a large collection of items. This collection contains a great many duplicates, and it will most likely be best to store some or all of ...
- 1,183
3
votes
2
answers
487
views
data structures for efficient/easy implementation of finite volume method for 2D Poisson equation
My question is about implementation alone.
Consider a square domain with regular square, cell centred finite
volumes. This is for the multiscale finite volume method (Jenny and Lunati)
I need to ...
- 435
2
votes
2
answers
11k
views
Implement the Huffman code in Python or Numpy?
The Huffman code is a way of compressing data streams by encoding the more frequent items with shorter words.
Here is a distribution on the letters A thru J and the code I obtained:
...
- 927
7
votes
2
answers
1k
views
adaptive Gauss-Kronrod quadrature with vector-valued integrand
So I'm trying to implement a Gauss-Kronrod adaptive quadrature. That is, I want to calculate
$$\int_a^b f(x) dx = \sum_i f(x_i) w_i$$
where f(x) is evaluated at multiple points at once for ...
- 223
1
vote
0
answers
356
views
Practical implementation of spatial binning for rectangular range queries
I have a bunch of polygons and a coarse uniform grid. I want to implement two different range queries, for a rectangle aligned with the uniform grid:
Does the rectangle intersect with any polygon at ...
- 2,131
11
votes
2
answers
1k
views
Data structures for finite volume code: Arrays vs Classes
I have to write a finite volume code for Magnetohydrodynamics (MHD). I have written numerical code before but not at this scale. I just wanted to ask which will be a good choice, using a data ...
- 531
8
votes
2
answers
4k
views
Proper data-structure and algorithm for 3-D Delaunay triangulation
I have worked out some poor code to achieve the goal of 3D Delauney triangulation(random points in E3), but the time consuming is huge, and when five points are exactly (or nearly due to the round-off ...
- 81
14
votes
5
answers
968
views
Repeated nearest neighbor calculation for millions of data points too slow
I have a dataset running into millions of data points in 3D. For the calculation I am doing, I need to calculate neighbor (range search) to each data point in a radius, try to fit a function, ...
5
votes
3
answers
202
views
Where do I find data to start a graph data structure to practice on?
I am interested in learning firsthand about graph data structures but have no data to put into the database. Can anyone recommend a source for a beginner to find graph data? (Preferably a source that ...
- 51
13
votes
2
answers
1k
views
What are some good data-types for unstructured cell-centered FVM CFD code?
I'm interested in an advice for efficient data structures for cell browsing in unstructured cell-based finite volume CFD.
One example that I encountered (in dolfyn cfd code) goes like this (I'll show ...
- 1,373
4
votes
2
answers
4k
views
Extracting a 2D matrix from a multidimensional array in C
In my c language program, I have to store multiple dense $m\times m$ matrices corresponding to gridpoints $x_i$ with $i=1,...,n$. I decided to create a three dimensional array $A\in R^{n\times m\...
- 11.8k
5
votes
3
answers
274
views
How to efficiently structure simulation data in memory for cells with varying degrees of freedom?
For a discontinuous Galerkin-based simulation I need to store cell-based simulation data in memory. Since the order of the polynomial approximation $N_p$ may vary between cells, I wonder what the most ...
