Octanions to the Rescue

Octanions to the Rescue: "

Click here for the most recent polymath3 research thread.

Xavier Dahan and Jean-Pierre Tillich’s Octanion-based Ramanujan Graphs with High Girth.

Michael Atiyah’s lecture at IAS physics last Friday was entertaining, educational and quite provocative.

The talk started with the following thesis: There are four fundamental forces of nature and there are four division rings over the reals. The real numbers, complex numbers, Quaternions and the Octanions. Atiyah expects that the Octanions will play a major role in physics and will allow a theory which accounts for gravitation. He described some specific steps in this direction and related ideas and connections. At the end of the talk, Atiyah’s thesis looked more plausible than in the beginning. His concluding line was: “you can regard what I say as nonsense, or you can claim that you know it already, but you cannot make these two claims together.” In any case, it looks that the people in the audience were rather impressed by and sympathetic to the Octanionic ideas of this wise energetic scientific tycoon.

The same day I received an email from Nati Linial. The subject was: “a good topic for your blog” and the email contained just a single link.

http://arxiv.org/PS_cache/arxiv/pdf/1011/1011.2642v1.pdf

Nati is my older academic brother and often I regard our relations as similar to typical relations between older and younger (biological) brothers. When he tells me what to do I often rebel, but usually at the end I do as he says and most of the times he is right.

So I waited a couple of hours before looking at the link. Indeed, 1011.2642v1.pdf is a great paper. It uses Octanions in place of Quaternions for the construction of Ramanujan graphs and describes a wonderful breakthrough in creating small graphs with large girth.

"

Optoelectronic and Excitonic Properties of Oligoacenes: Substantial Improvements from Range-Separated Time-Dependent Density Functional Theory

Optoelectronic and Excitonic Properties of Oligoacenes: Substantial Improvements from Range-Separated Time-Dependent Density Functional Theory: "

Journal of Chemical Theory and Computation

DOI: 10.1021/ct100529s

"

Accelerating Reaction-Diffusion Simulations with General-Purpose Graphics Processing Units.

Accelerating Reaction-Diffusion Simulations with General-Purpose Graphics Processing Units.: "Publication Date: 2010 Nov 9 PMID: 21062761
Authors: Vigelius, M. - Lane, A. - Meyer, B.
Journal: Bioinformatics

SUMMARY: We present a massively parallel stochastic simulation algorithm (SSA) for reaction-diffusion systems implemented on Graphics Processing Units (GPUs). These are designated chips optimized to process a high number of floating point operations in parallel, rendering them well-suited for a range of scientific high-performance computations. Newer GPU generations provide a high-level programming interface which turns them into General-Purpose Graphics Processing Units (GPGPUs). Our SSA exploits GPGPU architecture to achieve a performance gain of two orders of magnitude over the fastest existing implementations on conventional hardware. AVAILABILITY: The software is freely available at http://www.csse.monash.edu.au/~berndm/inchman/. CONTACT: Matthias.Vigelius@monash.edu SUPPLEMENTARY INFORMATION: Supplementary information is available at Bioinformatics online.

post to: CiteULike"

Static two-grid mixed finite-element approximations to the Navier-Stokes equations. (arXiv:1011.2972v1 [math.NA])

Static two-grid mixed finite-element approximations to the Navier-Stokes equations. (arXiv:1011.2972v1 [math.NA]): "

A two-grid scheme based on mixed finite-element approximations to the
incompressible Navier-Stokes equations is introduced and analyzed. In the first
level the standard mixed finite-element approximation over a coarse mesh is
computed. In the second level the approximation is postprocessed by solving a
discrete Oseen-type problem on a finer mesh. The two-level method is optimal in
the sense that, when a suitable value of the coarse mesh diameter is chosen, it
has the rate of convergence of the standard mixed finite-element method over
the fine mesh. Alternatively, it can be seen as a postprocessed method in which
the rate of convergence is increased by one unit with respect to the coarse
mesh. The analysis takes into account the loss of regularity at initial time of
the solution of the Navier-Stokes equations in absence of nonlocal
compatibility conditions. Some numerical experiments are shown.

"

Static two-grid mixed finite-element approximations to the Navier-Stokes equations. (arXiv:1011.2972v1 [math.NA])

Static two-grid mixed finite-element approximations to the Navier-Stokes equations. (arXiv:1011.2972v1 [math.NA]): "

A two-grid scheme based on mixed finite-element approximations to the
incompressible Navier-Stokes equations is introduced and analyzed. In the first
level the standard mixed finite-element approximation over a coarse mesh is
computed. In the second level the approximation is postprocessed by solving a
discrete Oseen-type problem on a finer mesh. The two-level method is optimal in
the sense that, when a suitable value of the coarse mesh diameter is chosen, it
has the rate of convergence of the standard mixed finite-element method over
the fine mesh. Alternatively, it can be seen as a postprocessed method in which
the rate of convergence is increased by one unit with respect to the coarse
mesh. The analysis takes into account the loss of regularity at initial time of
the solution of the Navier-Stokes equations in absence of nonlocal
compatibility conditions. Some numerical experiments are shown.

"

A posteriori error estimations for mixed finite-element approximations to the Navier-Stokes equations. (arXiv:1011.2878v1 [math.NA])

A posteriori error estimations for mixed finite-element approximations to the Navier-Stokes equations. (arXiv:1011.2878v1 [math.NA]): "

A posteriori estimates for mixed finite element discretizations of the
Navier-Stokes equations are derived. We show that the task of estimating the
error in the evolutionary Navier-Stokes equations can be reduced to the
estimation of the error in a steady Stokes problem. As a consequence, any
available procedure to estimate the error in a Stokes problem can be used to
estimate the error in the nonlinear evolutionary problem. A practical procedure
to estimate the error based on the so-called postprocessed approximation is
also considered. Both the semidiscrete (in space) and the fully discrete cases
are analyzed. Some numerical experiments are provided.

"

Convergence analysis of a partial differential algebraic system from coupling a semiconductor model to a circuit model

Convergence analysis of a partial differential algebraic system from coupling a semiconductor model to a circuit model: "Publication year: 2010
Source: Applied Numerical Mathematics, In Press, Accepted Manuscript, Available online 12 November 2010
Michael, Matthes , Caren, Tischendorf
We are interested in circuit simulation including distributed semiconductor models. The circuit itself is modeled by the modified nodal analysis. The stationary drift diffusion equations are used to describe the semiconductors. The complete system is then a partial differential-algebraic system. We discretize it first in space with finite elements and the Scharfetter-Gummel discretization. The resulting semi-discrete system can be analyzed as a differential-algebraic equation with properly stated leading term. We present topological index one criteria. They coincide with previous results for the non-discretized partial differential-algebraic equation. For the time discretization we use standard BDF methods (implicit Gear formulas). Finally we..."

Dissipativity of Runge–Kutta methods for Volterra functional differential equations☆

Dissipativity of Runge–Kutta methods for Volterra functional differential equations☆: "Publication year: 2010
Source: Applied Numerical Mathematics, In Press, Accepted Manuscript, Available online 12 November 2010
Liping, Wen , Yuexin, Yu , Shoufu, Li
This paper is concerned with the numerical dissipativity of nonlinear Volterra functional differential equations (VFDEs). We give some dissipativity results of Runge–Kutta methods when they are applied to VFDEs. These results provide unified theoretical foundation for the numerical dissipativity analysis of systems in ordinary differential equations (ODEs), delay differential equations (DDEs), integro-differential equations (IDEs), Volterra delay integro-differential equations (VDIDEs) and VFDEs of other type which appear in practice. Numerical examples are given to confirm our theoretical results."

Dual coordinate descent methods for logistic regression and maximum entropy models

Dual coordinate descent methods for logistic regression and maximum entropy models: "

Abstract

Most optimization methods for logistic regression or maximum entropy solve the primal problem. They range from iterative scaling,
coordinate descent, quasi-Newton, and truncated Newton. Less efforts have been made to solve the dual problem. In contrast,
for linear support vector machines (SVM), methods have been shown to be very effective for solving the dual problem. In this paper, we apply coordinate descent methods
to solve the dual form of logistic regression and maximum entropy. Interestingly, many details are different from the situation
in linear SVM. We carefully study the theoretical convergence as well as numerical issues. The proposed method is shown to be faster than
most state of the art methods for training logistic regression and maximum entropy.

• Content Type Journal Article
• DOI 10.1007/s10994-010-5221-8
• Authors
  
  
  • Hsiang-Fu Yu, Department of Computer Science, National Taiwan University, Taipei, 106 Taiwan
  • Fang-Lan Huang, Department of Computer Science, National Taiwan University, Taipei, 106 Taiwan
  • Chih-Jen Lin, Department of Computer Science, National Taiwan University, Taipei, 106 Taiwan
  
  

• Journal Machine Learning
• Online ISSN 1573-0565
• Print ISSN 0885-6125

"

Range Minima Queries with Respect to a Random Permutation, and Approximate Range Counting

Range Minima Queries with Respect to a Random Permutation, and Approximate Range Counting: "

Abstract

In approximate halfspace range counting, one is given a set P of n points in ℝ
^d
, and an ε>0, and the goal is to preprocess P into a data structure which can answer efficiently queries of the form: Given a halfspace h, compute an estimate N such that (1−ε)|P∩h|≤N≤(1+ε)|P∩h|.

Several recent papers have addressed this problem, including a study by Kaplan and Sharir (Proc. 17th Annu. ACM-SIAM Sympos.
Discrete Algo., pp. 484–493, 2006), which is based, as is the present paper, on Cohen’s technique for approximate range counting (Cohen in J. Comput. Syst.
Sci. 55:441–453, 1997). In this approach, one chooses a small number of random permutations of P, and then constructs, for each permutation π, a data structure that answers efficiently minimum range queries: Given a query halfspace h, find the minimum-rank element (according to π) in P∩h. By repeating this process for all chosen permutations, the approximate count can be obtained, with high probability, using
a certain averaging process over the minimum-rank outputs.

In the previous study, the authors have constructed such a data structure in ℝ³, using a combinatorial result about the overlay of minimization diagrams in a randomized incremental construction of lower
envelopes.

In the present work, we propose an alternative approach to the range-minimum problem, based on cuttings, which achieves better
performance. Specifically, it uses, for each permutation, O(n
^⌊d/2⌋(log log n)
^c
/log ^⌊d/2⌋
n) expected storage and preprocessing time, for some constant c, and answers a range-minimum query in O(log n) expected time. We also present a different approach, based on “antennas,” which is simple to implement, although the bounds
on its expected storage, preprocessing, and query costs are worse by polylogarithmic factors.

• Content Type Journal Article
• DOI 10.1007/s00454-010-9308-6
• Authors
  
  
  • Haim Kaplan, School of Computer Science, Tel Aviv University, Tel Aviv, 69978 Israel
  • Edgar Ramos, Department of Computer Science, Universidad Nacional de Colombia, Medellín, Colombia
  • Micha Sharir, School of Computer Science, Tel Aviv University, Tel Aviv, 69978 Israel
  
  

• Journal Discrete and Computational Geometry
• Online ISSN 1432-0444
• Print ISSN 0179-5376

"

Convergence and Smoothness of Nonlinear Lane–Riesenfeld Algorithms in the Functional Setting

Convergence and Smoothness of Nonlinear Lane–Riesenfeld Algorithms in the Functional Setting: "

Abstract

We investigate the Lane–Riesenfeld subdivision algorithm for uniform B-splines, when the arithmetic mean in the various steps
of the algorithm is replaced by nonlinear, symmetric, binary averaging rules. The averaging rules may be different in different
steps of the algorithm. We review the notion of a symmetric binary averaging rule, and we derive some of its relevant properties.
We then provide sufficient conditions on the nonlinear binary averaging rules used in the Lane–Riesenfeld algorithm that ensure
the convergence of the algorithm to a continuous function. We also show that, when the averaging rules are C
² with uniformly bounded second derivatives, then the limit is a C
¹ function. A canonical family of nonlinear, symmetric averaging rules, the p-averages, is presented, and the Lane–Riesenfeld algorithm with these averages is investigated.

• Content Type Journal Article
• DOI 10.1007/s10208-010-9080-2
• Authors
  
  
  • Nira Dyn, School of Mathematical Sciences, Tel Aviv University, Tel Aviv, 69978 Israel
  • Ron Goldman, Department of Computer Science, Rice University, Houston, TX 77251, USA
  
  

• Journal Foundations of Computational Mathematics
• Online ISSN 1615-3383
• Print ISSN 1615-3375

"

Superconvergence and Gradient Recovery of Linear Finite Elements for the LaplaceBeltrami Operator on General Surfaces

Superconvergence and Gradient Recovery of Linear Finite Elements for the LaplaceBeltrami Operator on General Surfaces: "Huayi Wei, Long Chen, and Yunqing Huang

Superconvergence results and several gradient recovery methods of finite element methods in flat spaces are generalized to the surface linear finite element method for the LaplaceBeltrami equation on general surfaces with mildly structured triangular meshes. For a large class of practically useful ... [SIAM J. Numer. Anal. 48, 1920 (2010)] published Thu Nov 11, 2010."

Chinese supercomputer named world's fastest

Chinese supercomputer named world's fastest: "China overtook the United States at the head of the world of supercomputing on Sunday when a survey ranked one of its machines the fastest on the planet."

Local-Structure-Preserving Discontinuous Galerkin Methods with Lax-Wendroff Type Time Discretizations for Hamilton-Jacobi Equations

Local-Structure-Preserving Discontinuous Galerkin Methods with Lax-Wendroff Type Time Discretizations for Hamilton-Jacobi Equations: "

Abstract

In this paper, a family of high order numerical methods are designed to solve the Hamilton-Jacobi equation for the viscosity
solution. In particular, the methods start with a hyperbolic conservation law system closely related to the Hamilton-Jacobi
equation. The compact one-step one-stage Lax-Wendroff type time discretization is then applied together with the local-structure-preserving
discontinuous Galerkin spatial discretization. The resulting methods have lower computational complexity and memory usage
on both structured and unstructured meshes compared with some standard numerical methods, while they are capable of capturing
the viscosity solutions of Hamilton-Jacobi equations accurately and reliably. A collection of numerical experiments is presented
to illustrate the performance of the methods.

• Content Type Journal Article
• DOI 10.1007/s10915-010-9434-6
• Authors
  
  
  • Wei Guo, Department of Mathematics, Nanjing University, Nanjing, Jiangsu 210093, P.R. China
  • Fengyan Li, Department of Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, NY 12180, USA
  • Jianxian Qiu, Department of Mathematics, Nanjing University, Nanjing, Jiangsu 210093, P.R. China
  
  

• Journal Journal of Scientific Computing
• Online ISSN 1573-7691
• Print ISSN 0885-7474

"

Google acusa a Oracle de manipular evidencia en demanda por Android

Published with Blogger-droid v1.6.5