All Questions

9,886 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 (...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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?...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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. ...
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 ...
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.
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 ...
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 ...
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 ...
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....
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 ...
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 ...
239 views

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 ...
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 ...
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 ...
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 ...
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. ...
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 ...
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}$ ...
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 ...
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 ...
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 ...
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,...
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 ...
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)$ ...
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?
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 ...
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 ...