All Questions

Filter by
Sorted by
Tagged with
5
votes
2answers
489 views

How to parallelize a banded direct solver?

I have a linear system whose matrix that is diagonally dominant, non-symmetric, but banded. Since the band-radius is 2 (producing only 5 variables per equation), a banded direct solver (gaussian ...
6
votes
1answer
342 views

What efficient algorithms are there to generate arbitrary dimensional meshes of simplices?

I know that delaunay triangulation can be extended into arbitrary dimensions by solving the convex hull problem in $(p+1)$ dimensions and projecting the lower hull into dimension $p$ to obtain a mesh ...
4
votes
3answers
299 views

How to fill a 2D set over a cartesian lattice with as few rectangles as possible?

Suppose I have a black and white image (composed of binary pixel values in a 2D cartesian array) that contains an irregular, nonconvex shape. Let's further suppose that the shape is one connected ...
15
votes
1answer
2k views

Can a Krylov subspace method be used as a smoother for multigrid?

As far as I am aware, multigrid solvers use iterative smoothers such as Jacobi, Gauss-Seidel, and SOR to dampen the error at various frequencies. Could a Krylov subspace method (like conjugate ...
11
votes
1answer
1k views

Library for Fourier transform on triangle lattice

I am looking for reasonably fast implementations of the discrete Fourier transform (DFT) on a 2D triangular or hexagonal lattice. I would appreciate pointers to such implementations (especially ones ...
6
votes
2answers
423 views

How can I reduce the communication bottleneck of a parallel explicit finite difference scheme?

Suppose i was trying to solve a parabolic PDE (heat equation) on a rectangular domain using an explicit finite difference scheme. I am storing my solution vector in a matrix form (because it closely ...
11
votes
1answer
2k views

How can one parallelize a multigrid method for solving a linear system of equations?

As I understand it, the multigrid method solves a linear system by solving a coarser version of the same problem (there by eliminating low frequency error) then projecting back to the fine grid to ...
9
votes
7answers
1k views

Is there a standard rating system for scientific journal publications?

I have heard that some journals are rated more highly than others. Is this true? And if so, what are the criteria for judging the value of one peer reviewed journal over another? How do I find out ...
6
votes
3answers
714 views

Surface Mesh Library

I'm thinking a bit about the Front Tracking method used for simulation of Two phase flow with sharp interfaces. The literature tells me that the main issue is the surface mesh representation (...
2
votes
3answers
1k views

Computational Complexity of Image Segmentation algorithms

I have a question. I need to calculate the computational complexity of image segmentation algorithms. Can anyone please help me? For example, I have a screen-size picture with white background ...
4
votes
2answers
2k views

How do I compile a program that contains both MPI and OPENMP

I have a fortran 90 code that distributes blocks of computations (from a matrix) to multiple nodes in a cluster using MPI, but in each node, the for loops are executed in parallel using openmp. I ...
12
votes
3answers
2k views

finite volume method: unstructured mesh vs octree adaptation + cell cutting

I'm working with the OpenFOAM C++ Computational Continuum Mechanics library (it can deal with fluid-solid interaction, MHD flows...) which uses arbitrary unstructured meshes. This was driven by the ...
3
votes
2answers
1k views

Looking for a library or algorithms to perfom clipping 3D unstructured meshes by a set of surfaces

We have a 3D (volume) unstructured, possibly hybrid, degenerative irregular mesh data structure that we are capable of generating (mostly composed of hexahedra and general polyhedra, using a mix of ...
10
votes
3answers
841 views

Complex numerical analysis

What numerical analysis situations become more/less stable, have faster/slower convergence, or are otherwise quite different when dealing with functions of complex variable instead of functions of a ...
7
votes
2answers
2k views

Reference implementation of Nédélec-Elements

Does anybody know of an implementation of Nédélec elements that does not come along with a huge bulk of additional software? Is there a small library written in a language like Python, Matlab, or ...
12
votes
4answers
1k views

Scalability of Fast Fourier Transform (FFT)

To use the Fast Fourier Transform (FFT) on uniformly sampled data, e.g. in connection with PDE solvers, it is well known that the FFT is an $\mathcal{O}(n\log(n)$) algorithm. How well do the FFT scale ...
10
votes
3answers
579 views

Which is computed faster, $a^b$, $\log_a c$ or $\sqrt[b]{c}$?

Which is computed faster, $a^b$ or $\log_a c$ or $\sqrt[b]{c}$? $a$, $b$ and $c$ are positive reals with $b>1$. What kinds of algorithms will you use in the comparison? What are their complexities?...
3
votes
0answers
117 views

Up-/downdating methods for a series of normal equations

In an application I have to solve a series of positive definite linear systems of the form $A^TA x = A^Tb$ (i.e. normal equations). The next system is obtained from the previous one by adding and/or ...
16
votes
1answer
6k views

How to derive the Weak Formulation of a Partial Differential Equation for Finite Element Method?

I have taken a basic introduction to Finite Element Method, which did not emphasize a sophisticated understanding of a 'weak formulation'. I understand that with the galerkin method, we multiply both ...
11
votes
5answers
750 views

Is it preferable to concentrate on studying math or computation?

Concurrent to my research on Krylov Subspace Methods, I have the option of exploring mathematics behind HPC a step ahead or the theory of computation (hardware, OS, compilers etc.). Currently, I know ...
3
votes
1answer
553 views

Fitting a grid to an STM image

Suppose I have a scan from an STM image (very much like the things you see here). Suppose I have a simple square lattice with lattice parameter a. What I'd like to do is to numerically find the ...
12
votes
1answer
4k views

Efficient solution of mixed integer linear programs

Many important problems can be expressed as a mixed integer linear program. Unfortunately computing the optimal solution to this class of problems is NP-Complete. Luckily there are approximation ...
13
votes
2answers
874 views

When is automatic differentiation cheap?

Automatic differentiation allows us to numerically evaluate the derivative of a program on a particular input. There is a theorem that this computation can done at a cost less than five times the cost ...
8
votes
3answers
2k views

Scientific Programming on Mac using Objective-C/Cocoa for MATLAB Users

I want to get started on scientific programming on the Mac using Objective-C. I am very familiar with MATLAB which makes it easy to store complex-valued waveform data in vectors and generating plots. ...
18
votes
5answers
6k views

State of the Mac OS in Scientific Computing and HPC

Back towards the dawn of OS X, there seemed to be a great deal of hubbub, at least in the Mac world (I was nowhere near scientific computing at the time) about the Mac OS as a platform for scientific ...
18
votes
5answers
3k views

What is the advantage of multigrid over domain decomposition preconditioners, and vice versa?

This is mostly aimed for elliptic PDEs over convex domains, so that I can get a good overview of the two methods.
5
votes
0answers
135 views

Probabilistic algorithms for matrix approximation

Considering regular matrix approximation inequality || $A - QQ^TA $|| < e where we try to approximate matrix $A$ by a lower rank orthonormal matrix $Q$. I've read an article on probabilistic ...
8
votes
1answer
3k views

What is a good stop criterion when using an iterative method to find eigenvalues?

I read this answer, and realized I have been using the difference between sucessive iterates to define a stop criterion for an iterative method of finding eigenvalues/vectors. What are good stop ...
4
votes
2answers
2k views

Solution oscillations with a small timestep in backward Euler

I am using backward Euler in a FEM scheme for a convection-diffusion problem. On a given mesh, I can take arbitrarily large time steps, as expected. But if I decrease time step, at some point it will ...
11
votes
1answer
320 views

What are the possible numerical schemes for a diffusion equation with a nonlinear reaction term?

For some simple convex domain $\Omega$ in 2D, we have some $u(x)$ satisfying the following equation: $$ -\mathrm{div}(A\nabla u)+cu^n = f $$ with certain Dirichlet and/or Neumann boundary conditions....
5
votes
1answer
148 views

Looking for an understandable discussion of creating Maximum Entropy classifiers

Texts, articles, and papers on Maximum Entropy Classifiers tend to come in two varieties: the more popular "upper level", and the more technical. The popular variety are good at explaining the ...
28
votes
2answers
13k views

Why is my iterative linear solver not converging?

What can go wrong when using preconditoned Krylov methods from KSP (PETSc's linear solver package) to solve a sparse linear system such as those obtained by discretizing and linearizing partial ...
10
votes
1answer
239 views

Quadrature rules, methodologies, and references

There is at least one quite comprehensive encyclopaedia of quadrature rules that doesn't seem to have been updated in quite a while and has restricted access. This source refers to several classical ...
17
votes
2answers
868 views

How can I choose a good Riemann solver when numerically solving a system of hyperbolic PDEs?

Many numerical methods for hyperbolic PDEs are based on the use of Riemann solvers. Such solvers are essential for accurately capturing shock waves. There are a range of such solvers available for ...
10
votes
2answers
1k views

Are 8 Gauss points required for second order hexahedral finite elements?

Is it possible to get second order accuracy for hexahedral finite elements with fewer than 8 Gauss points without introducing unphysical modes? A single central Gauss point introduces an unphysical ...
2
votes
2answers
478 views

Is there a Moore's law for floating-point precision, and what would it imply?

Moore's law states that the number of transistors on an integrated circuit grow exponentially, roughly doubling at a period of 20 months. This affects the amount of memory available and the speed of ...
3
votes
1answer
445 views

Testing a simple polygon for monotonicity in linear time question

I'm looking for the algorithm of Preparata and Supowit for testing a simple polygon for monotonicity in linear time. I've found it referenced in many textbooks but I can't find the algorithm itself. ...
5
votes
3answers
1k views

Implementing Euler's method for initial value ODEs

In my physics class, I had to calculate the trajectory of a projectile that was fired (very fast) with $v_0$ in an angle off a planet (radius $R$, mass $M$) from the surface. The projectile would ...
9
votes
2answers
2k views

numerical integration with possible division by 'zero'

I am trying to integrate $$\int^1_0 t^{2n+2}\exp\left({\frac{\alpha r_0}{t}}\right)dt$$ which is a simple transformation of $$\int^{\infty}_1 x^{2n}\exp(-\alpha r_0 x)dx$$ using $t = \frac1{x}$ ...
7
votes
2answers
775 views

Is it possible to dynamically resize a sparse matrix in the Petsc library?

This may be a Petsc newbie question, but... I'm using Petsc to solve a large sparse linear system. The initial creation of the matrix is fairly slow, which I'm given to understand is largely due to ...
4
votes
4answers
358 views

Approximate a distribution function from a finite sample

Say I have a simulation that produces a single floating point number as a result, and a different number is produced each time the simulation runs. These numbers are randomly distributed according to ...
5
votes
1answer
216 views

Discretization of Classical Density Functional Theory (CDFT) problems

I formulate questions about ion densities in biological and materials problems using Classical Density Functional Theory, as in this paper which is also on the arXiv. The discretization in that paper ...
1
vote
0answers
58 views

Assembled human ESTs for annotation

I am annotating protein-coding genes in a region of the human genome and am looking for a set of assembled ESTs I can use as evidence for constructing gene models. A quick search of NCBI's SRA shows 4,...
17
votes
2answers
1k views

Which libraries have good high-level support for multigrid?

I'm planning to use multigrid to calulate some eigenvalues and vectors, and I noticed PETSc has high-level support for multigrid. The PETSc documentation says that this part of PETSc should not be ...
4
votes
2answers
373 views

best way to optimize a function with linear/non-linear parameters

I am trying to fit some raw data using a function of the form $f(r) = \sum_{i=1}^{K} d_kS_k(n_k,\alpha_k,r)$ where $S_k(n_k,\alpha_k,r) = \frac{\alpha_k ^{n_k+3}}{(n_k+2)!}r^{n_k}\exp(-\alpha_kr)$ ...
3
votes
3answers
245 views

Evaluating $\binom{100}{i}a^i(1-a)^{(100-i)}$ in GMP-GNU

I want to calculate $\binom{100}{i}a^i(1-a)^{(100-i)}$ for different $i$ with $a=0.001$ using GMP-GNU. How can this be done?
8
votes
2answers
373 views

What is a good way to understand the overall structure of a code base?

Sometimes it is useful in my work to modify someone else open-source code or find out how to develop specific things for your own application. However, not all software have good documentation. What ...
4
votes
1answer
98 views

Applicability of combinatorial and support preconditioner

There are several correspondences between matrices and graphs, e.g., each matrix is the adjacancy matrix of a weighted graph. The terms support preconditioner or combinatorial preconditioner refer to ...
12
votes
2answers
2k views

Is there an open source set of ODE solvers for C that use the native C99 complex type?

I've been using GSL as the foundation of many of my simulations, but it's a little bit overkill for my purposes and it defines its own complex type for legacy reasons. Rather than code my own Runge-...
21
votes
3answers
2k views

Parallel I/O options, in particular parallel HDF5

I have an application that can be trivially parallelized but its performance is to a large extent I/O bound. The application reads a single input array stored in a file that is typically 2-5 GB in ...

15 30 50 per page