We investigate the properties of the Hybrid Monte-Carlo algorithm (HMC) in
high dimensions. HMC develops a Markov chain reversible w.r.t. a given target
distribution $Pi$ by using separable Hamiltonian dynamics with potential
$-logPi$. The additional momentum variables are chosen at random from the
Boltzmann distribution and the continuous-time Hamiltonian dynamics are then
discretised using the leapfrog scheme. The induced bias is removed via a
Metropolis-Hastings accept/reject rule. In the simplified scenario of
independent, identically distributed components, we prove that, to obtain an
$mathcal{O}(1)$ acceptance probability as the dimension $d$ of the state space
tends to $infty$, the leapfrog step-size $h$ should be scaled as $h= l imes
d^{-1/4}$. Therefore, in high dimensions, HMC requires $mathcal{O}(d^{1/4})$
steps to traverse the state space. We also identify analytically the
asymptotically optimal acceptance probability, which turns out to be 0.651 (to
three decimal places). This is the choice which optimally balances the cost of
generating a proposal, which {em decreases} as $l$ increases, against the cost
related to the average number of proposals required to obtain acceptance, which
{em increases} as $l$ increases.
martes, 26 de enero de 2010
Optimal tuning of the Hybrid Monte-Carlo Algorithm. (arXiv:1001.4460v1 [math.PR])
Solving Schubert Problems with Littlewood-Richardson Homotopies. (arXiv:1001.4125v1 [math.NA])
We present a new numerical homotopy continuation algorithm for finding all
solutions to Schubert problems on Grassmannians. This Littlewood-Richardson
homotopy is based on Vakil's geometric proof of the Littlewood-Richardson rule.
Its start solutions are given by linear equations and they are tracked through
a sequence of homotopies encoded by certain checker configurations to find the
solutions to a given Schubert problem. For generic Schubert problems the number
of paths tracked is optimal. The Littlewood-Richardson homotopy algorithm is
implemented using the path trackers of the software package PHCpack.
Numerical Studies of Three-dimensional Stochastic Darcy’s Equation and Stochastic Advection-Diffusion-Dispersion Equation
Abstract Solute transport in randomly heterogeneous porous media is commonly described by stochastic flow and advection-dispersion
equations with a random hydraulic conductivity field. The statistical distribution of conductivity of engineered and naturally
occurring porous material can vary, depending on its origin. We describe solutions of a three-dimensional stochastic advection-dispersion
equation using a probabilistic collocation method (PCM) on sparse grids for several distributions of hydraulic conductivity.
Three random distributions of log hydraulic conductivity are considered: uniform, Gaussian, and truncated Gaussian (beta).
Log hydraulic conductivity is represented by a Karhunen-Loève (K-L) decomposition as a second-order random process with an
exponential covariance function. The convergence of PCM has been demonstrated. It appears that the accuracy in both the mean
and the standard deviation of PCM solutions can be improved by using the Jacobi-chaos representing the truncated Gaussian
distribution rather than the Hermite-chaos for the Gaussian distribution. The effect of type of distribution and parameters
such as the variance and correlation length of log hydraulic conductivity and dispersion coefficient on leading moments of
the advection velocity and solute concentration was investigated.
equations with a random hydraulic conductivity field. The statistical distribution of conductivity of engineered and naturally
occurring porous material can vary, depending on its origin. We describe solutions of a three-dimensional stochastic advection-dispersion
equation using a probabilistic collocation method (PCM) on sparse grids for several distributions of hydraulic conductivity.
Three random distributions of log hydraulic conductivity are considered: uniform, Gaussian, and truncated Gaussian (beta).
Log hydraulic conductivity is represented by a Karhunen-Loève (K-L) decomposition as a second-order random process with an
exponential covariance function. The convergence of PCM has been demonstrated. It appears that the accuracy in both the mean
and the standard deviation of PCM solutions can be improved by using the Jacobi-chaos representing the truncated Gaussian
distribution rather than the Hermite-chaos for the Gaussian distribution. The effect of type of distribution and parameters
such as the variance and correlation length of log hydraulic conductivity and dispersion coefficient on leading moments of
the advection velocity and solute concentration was investigated.
- Content Type Journal Article
- DOI 10.1007/s10915-010-9346-5
- Authors
- G. Lin, Pacific Northwest National Laboratory Computational Mathematics 902 Battelle Blvd. Box 999 Richland WA 99352 USA
- A. M. Tartakovsky, Pacific Northwest National Laboratory Computational Mathematics 902 Battelle Blvd. Box 999 Richland WA 99352 USA
- Journal Journal of Scientific Computing
- Online ISSN 1573-7691
- Print ISSN 0885-7474
A Compact Fourth Order Scheme for the Helmholtz Equation in Polar Coordinates
Abstract In many problems, one wishes to solve the Helmholtz equation in cylindrical or spherical coordinates which introduces variable
coefficients within the differentiated terms. Fourth order accurate methods are desirable to reduce pollution and dispersion
errors and so alleviate the points-per-wavelength constraint. However, the variable coefficients renders existing fourth order
finite difference methods inapplicable. We develop a new compact scheme that is provably fourth order accurate even for these
problems. The resulting system of finite difference equations is solved by a separation of variables technique based on the
FFT. Moreover, in the r direction the unbounded domain is replaced by a finite domain, and an exact artificial boundary condition is specified as
a closure. This global boundary condition fits naturally into the inversion of the linear system. We present numerical results
that corroborate the fourth order convergence rate for several scattering problems.
coefficients within the differentiated terms. Fourth order accurate methods are desirable to reduce pollution and dispersion
errors and so alleviate the points-per-wavelength constraint. However, the variable coefficients renders existing fourth order
finite difference methods inapplicable. We develop a new compact scheme that is provably fourth order accurate even for these
problems. The resulting system of finite difference equations is solved by a separation of variables technique based on the
FFT. Moreover, in the r direction the unbounded domain is replaced by a finite domain, and an exact artificial boundary condition is specified as
a closure. This global boundary condition fits naturally into the inversion of the linear system. We present numerical results
that corroborate the fourth order convergence rate for several scattering problems.
- Content Type Journal Article
- DOI 10.1007/s10915-010-9348-3
- Authors
- S. Britt, North Carolina State University Department of Mathematics Box 8205 Raleigh NC 27695 USA
- S. Tsynkov, North Carolina State University Department of Mathematics Box 8205 Raleigh NC 27695 USA
- E. Turkel, Tel Aviv University School of Mathematical Sciences Ramat Aviv Tel Aviv 69978 Israel
- Journal Journal of Scientific Computing
- Online ISSN 1573-7691
- Print ISSN 0885-7474
A note on the O(n)-storage implementation of the GKO algorithm and its adaptation to Trummer-like matrices
Abstract We propose a new O(n)-space implementation of the GKO-Cauchy algorithm for the solution of linear systems where the coefficient matrix is Cauchy-like.
Moreover, this new algorithm makes a more efficient use of the processor cache memory; for matrices of size larger than n ≈ 500–1,000, it outperforms the customary GKO algorithm. We present an applicative case of Cauchy-like matrices with non-reconstructible
main diagonal. In this special instance, the O(n) space algorithms can be adapted nicely to provide an efficient implementation of basic linear algebra operations in terms
of the low displacement-rank generators.
Moreover, this new algorithm makes a more efficient use of the processor cache memory; for matrices of size larger than n ≈ 500–1,000, it outperforms the customary GKO algorithm. We present an applicative case of Cauchy-like matrices with non-reconstructible
main diagonal. In this special instance, the O(n) space algorithms can be adapted nicely to provide an efficient implementation of basic linear algebra operations in terms
of the low displacement-rank generators.
- Content Type Journal Article
- Category Original Paper
- DOI 10.1007/s11075-010-9361-5
- Authors
- Federico Poloni, Scuola Normale Superiore Piazza dei Cavalieri, 7 56126 Pisa Italy
- Journal Numerical Algorithms
- Online ISSN 1572-9265
- Print ISSN 1017-1398
An O(h6) numerical solution of general nonlinear fifth-order two point boundary value problems
Abstract A sixth-order numerical scheme is developed for general nonlinear fifth-order two point boundary-value problems. The standard
sextic spline for the solution of fifth order two point boundary-value problems gives only O(h
2) accuracy and leads to non-optimal approximations. In order to derive higher orders of accuracy, high order perturbations
of the problem are generated and applied to construct the numerical algorithm. O(h
6) global error estimates obtained for these problems. The convergence properties of the method is studied. This scheme has
been applied to the system of nonlinear fifth order two-point boundary value problem too. Numerical results are given to illustrate
the efficiency of the proposed method computationally. Results from the numerical experiments, verify the theoretical behavior
of the orders of convergence.
sextic spline for the solution of fifth order two point boundary-value problems gives only O(h
2) accuracy and leads to non-optimal approximations. In order to derive higher orders of accuracy, high order perturbations
of the problem are generated and applied to construct the numerical algorithm. O(h
6) global error estimates obtained for these problems. The convergence properties of the method is studied. This scheme has
been applied to the system of nonlinear fifth order two-point boundary value problem too. Numerical results are given to illustrate
the efficiency of the proposed method computationally. Results from the numerical experiments, verify the theoretical behavior
of the orders of convergence.
- Content Type Journal Article
- Category Original Paper
- DOI 10.1007/s11075-010-9362-4
- Authors
- Jalil Rashidinia, Iran University of Science & Technology Narmak School of Mathematics Tehran 16844-13114 Iran
- M. Ghasemi, Iran University of Science & Technology Narmak School of Mathematics Tehran 16844-13114 Iran
- R. Jalilian, Ilam University Department of Mathematics P.O. Box 69315-516 Ilam Iran
- Journal Numerical Algorithms
- Online ISSN 1572-9265
- Print ISSN 1017-1398
A variable step-size control algorithm for the weak approximation of stochastic differential equations
Abstract In this paper, we propose two local error estimates based on drift and diffusion terms of the stochastic differential equations
in order to determine the optimal step-size for the next stage in an adaptive variable step-size algorithm. These local error
estimates are based on the weak approximation solution of stochastic differential equations with one-dimensional and multi-dimensional
Wiener processes. Numerical experiments are presented to illustrate the effectiveness of this approach in the weak approximation
of several standard test problems including SDEs with small noise and scalar and multi-dimensional Wiener processes.
in order to determine the optimal step-size for the next stage in an adaptive variable step-size algorithm. These local error
estimates are based on the weak approximation solution of stochastic differential equations with one-dimensional and multi-dimensional
Wiener processes. Numerical experiments are presented to illustrate the effectiveness of this approach in the weak approximation
of several standard test problems including SDEs with small noise and scalar and multi-dimensional Wiener processes.
- Content Type Journal Article
- Category Original Paper
- DOI 10.1007/s11075-010-9363-3
- Authors
- A. Valinejad, Tarbiat Modares University Department of Mathematics P.O. Box 14115-175 Tehran Iran
- S. Mohammad Hosseini, Tarbiat Modares University Department of Mathematics P.O. Box 14115-175 Tehran Iran
- Journal Numerical Algorithms
- Online ISSN 1572-9265
- Print ISSN 1017-1398
A binary powering Schur algorithm for computing primary matrix roots
Abstract An algorithm for computing primary roots of a nonsingular matrix A is presented. In particular, it computes the principal root of a real matrix having no nonpositive real eigenvalues, using
real arithmetic. The algorithm is based on the Schur decomposition of A and has an order of complexity lower than the customary Schur based algorithm, namely the Smith algorithm.
real arithmetic. The algorithm is based on the Schur decomposition of A and has an order of complexity lower than the customary Schur based algorithm, namely the Smith algorithm.
- Content Type Journal Article
- Category Original Paper
- DOI 10.1007/s11075-009-9357-1
- Authors
- Federico Greco, Università di Perugia Dipartimento di Matematica e Informatica Via Vanvitelli 1 06123 Perugia Italy
- Bruno Iannazzo, Università di Perugia Dipartimento di Matematica e Informatica Via Vanvitelli 1 06123 Perugia Italy
- Journal Numerical Algorithms
- Online ISSN 1572-9265
- Print ISSN 1017-1398
A Kantorovich-type convergence analysis of the Newton–Josephy method for solving variational inequalities
Abstract We present a Kantorovich-type semilocal convergence analysis of the Newton–Josephy method for solving a certain class of variational
inequalities. By using a combination of Lipschitz and center-Lipschitz conditions, and our new idea of recurrent functions,
we provide an analysis with the following advantages over the earlier works (Wang 2009, Wang and Shen, Appl Math Mech 25:1291–1297, 2004) (under the same or less computational cost): weaker sufficient convergence conditions, larger convergence domain, finer
error bounds on the distances involved, and an at least as precise information on the location of the solution.
inequalities. By using a combination of Lipschitz and center-Lipschitz conditions, and our new idea of recurrent functions,
we provide an analysis with the following advantages over the earlier works (Wang 2009, Wang and Shen, Appl Math Mech 25:1291–1297, 2004) (under the same or less computational cost): weaker sufficient convergence conditions, larger convergence domain, finer
error bounds on the distances involved, and an at least as precise information on the location of the solution.
- Content Type Journal Article
- Category Original Paper
- DOI 10.1007/s11075-010-9364-2
- Authors
- Ioannis K. Argyros, Cameron University Department of Mathematics Sciences Lawton OK 73505 USA
- Saïd Hilout, Poitiers University Laboratoire de Mathématiques et Applications Bd. Pierre et Marie Curie, Téléport 2 B.P. 30179 86962 Futuroscope Chasseneuil Cedex France
- Journal Numerical Algorithms
- Online ISSN 1572-9265
- Print ISSN 1017-1398
- Journal Volume Volume -1
- Journal Issue Volume -1, Online First / January, 2010
Suscribirse a:
Entradas (Atom)