The development of an algebraic multigrid algorithm for symmetric positive definite linear systems
Energy Technology Data Exchange (ETDEWEB)
Vanek, P.; Mandel, J.; Brezina, M. [Univ. of Colorado, Denver, CO (United States)
1996-12-31
An algebraic multigrid algorithm for symmetric, positive definite linear systems is developed based on the concept of prolongation by smoothed aggregation. Coarse levels are generated automatically. We present a set of requirements motivated heuristically by a convergence theory. The algorithm then attempts to satisfy the requirements. Input to the method are the coefficient matrix and zero energy modes, which are determined from nodal coordinates and knowledge of the differential equation. Efficiency of the resulting algorithm is demonstrated by computational results on real world problems from solid elasticity, plate blending, and shells.
Toward robust scalable algebraic multigrid solvers
International Nuclear Information System (INIS)
Waisman, Haim; Schroder, Jacob; Olson, Luke; Hiriyur, Badri; Gaidamour, Jeremie; Siefert, Christopher; Hu, Jonathan Joseph; Tuminaro, Raymond Stephen
2010-01-01
This talk highlights some multigrid challenges that arise from several application areas including structural dynamics, fluid flow, and electromagnetics. A general framework is presented to help introduce and understand algebraic multigrid methods based on energy minimization concepts. Connections between algebraic multigrid prolongators and finite element basis functions are made to explored. It is shown how the general algebraic multigrid framework allows one to adapt multigrid ideas to a number of different situations. Examples are given corresponding to linear elasticity and specifically in the solution of linear systems associated with extended finite elements for fracture problems.
Codd, A. L.; Gross, L.
2018-03-01
We present a new inversion method for Electrical Resistivity Tomography which, in contrast to established approaches, minimizes the cost function prior to finite element discretization for the unknown electric conductivity and electric potential. Minimization is performed with the Broyden-Fletcher-Goldfarb-Shanno method (BFGS) in an appropriate function space. BFGS is self-preconditioning and avoids construction of the dense Hessian which is the major obstacle to solving large 3-D problems using parallel computers. In addition to the forward problem predicting the measurement from the injected current, the so-called adjoint problem also needs to be solved. For this problem a virtual current is injected through the measurement electrodes and an adjoint electric potential is obtained. The magnitude of the injected virtual current is equal to the misfit at the measurement electrodes. This new approach has the advantage that the solution process of the optimization problem remains independent to the meshes used for discretization and allows for mesh adaptation during inversion. Computation time is reduced by using superposition of pole loads for the forward and adjoint problems. A smoothed aggregation algebraic multigrid (AMG) preconditioned conjugate gradient is applied to construct the potentials for a given electric conductivity estimate and for constructing a first level BFGS preconditioner. Through the additional reuse of AMG operators and coarse grid solvers inversion time for large 3-D problems can be reduced further. We apply our new inversion method to synthetic survey data created by the resistivity profile representing the characteristics of subsurface fluid injection. We further test it on data obtained from a 2-D surface electrode survey on Heron Island, a small tropical island off the east coast of central Queensland, Australia.
Layout optimization with algebraic multigrid methods
Regler, Hans; Ruede, Ulrich
1993-01-01
Finding the optimal position for the individual cells (also called functional modules) on the chip surface is an important and difficult step in the design of integrated circuits. This paper deals with the problem of relative placement, that is the minimization of a quadratic functional with a large, sparse, positive definite system matrix. The basic optimization problem must be augmented by constraints to inhibit solutions where cells overlap. Besides classical iterative methods, based on conjugate gradients (CG), we show that algebraic multigrid methods (AMG) provide an interesting alternative. For moderately sized examples with about 10000 cells, AMG is already competitive with CG and is expected to be superior for larger problems. Besides the classical 'multiplicative' AMG algorithm where the levels are visited sequentially, we propose an 'additive' variant of AMG where levels may be treated in parallel and that is suitable as a preconditioner in the CG algorithm.
Parallel Element Agglomeration Algebraic Multigrid and Upscaling Library
Energy Technology Data Exchange (ETDEWEB)
2017-10-24
ParELAG is a parallel C++ library for numerical upscaling of finite element discretizations and element-based algebraic multigrid solvers. It provides optimal complexity algorithms to build multilevel hierarchies and solvers that can be used for solving a wide class of partial differential equations (elliptic, hyperbolic, saddle point problems) on general unstructured meshes. Additionally, a novel multilevel solver for saddle point problems with divergence constraint is implemented.
A survey of parallel multigrid algorithms
Chan, Tony F.; Tuminaro, Ray S.
1987-01-01
A typical multigrid algorithm applied to well-behaved linear-elliptic partial-differential equations (PDEs) is described. Criteria for designing and evaluating parallel algorithms are presented. Before evaluating the performance of some parallel multigrid algorithms, consideration is given to some theoretical complexity results for solving PDEs in parallel and for executing the multigrid algorithm. The effect of mapping and load imbalance on the partial efficiency of the algorithm is studied.
A Parallel Algebraic Multigrid Solver on Graphics Processing Units
Haase, Gundolf
2010-01-01
The paper presents a multi-GPU implementation of the preconditioned conjugate gradient algorithm with an algebraic multigrid preconditioner (PCG-AMG) for an elliptic model problem on a 3D unstructured grid. An efficient parallel sparse matrix-vector multiplication scheme underlying the PCG-AMG algorithm is presented for the many-core GPU architecture. A performance comparison of the parallel solver shows that a singe Nvidia Tesla C1060 GPU board delivers the performance of a sixteen node Infiniband cluster and a multi-GPU configuration with eight GPUs is about 100 times faster than a typical server CPU core. © 2010 Springer-Verlag.
Analysis of a parallel multigrid algorithm
Chan, Tony F.; Tuminaro, Ray S.
1989-01-01
The parallel multigrid algorithm of Frederickson and McBryan (1987) is considered. This algorithm uses multiple coarse-grid problems (instead of one problem) in the hope of accelerating convergence and is found to have a close relationship to traditional multigrid methods. Specifically, the parallel coarse-grid correction operator is identical to a traditional multigrid coarse-grid correction operator, except that the mixing of high and low frequencies caused by aliasing error is removed. Appropriate relaxation operators can be chosen to take advantage of this property. Comparisons between the standard multigrid and the new method are made.
Discrete Fourier analysis of multigrid algorithms
van der Vegt, Jacobus J.W.; Rhebergen, Sander
2011-01-01
The main topic of this report is a detailed discussion of the discrete Fourier multilevel analysis of multigrid algorithms. First, a brief overview of multigrid methods is given for discretizations of both linear and nonlinear partial differential equations. Special attention is given to the
Some multigrid algorithms for SIMD machines
Energy Technology Data Exchange (ETDEWEB)
Dendy, J.E. Jr. [Los Alamos National Lab., NM (United States)
1996-12-31
Previously a semicoarsening multigrid algorithm suitable for use on SIMD architectures was investigated. Through the use of new software tools, the performance of this algorithm has been considerably improved. The method has also been extended to three space dimensions. The method performs well for strongly anisotropic problems and for problems with coefficients jumping by orders of magnitude across internal interfaces. The parallel efficiency of this method is analyzed, and its actual performance on the CM-5 is compared with its performance on the CRAY-YMP. A standard coarsening multigrid algorithm is also considered, and we compare its performance on these two platforms as well.
Large-Scale Parallel Viscous Flow Computations using an Unstructured Multigrid Algorithm
Mavriplis, Dimitri J.
1999-01-01
The development and testing of a parallel unstructured agglomeration multigrid algorithm for steady-state aerodynamic flows is discussed. The agglomeration multigrid strategy uses a graph algorithm to construct the coarse multigrid levels from the given fine grid, similar to an algebraic multigrid approach, but operates directly on the non-linear system using the FAS (Full Approximation Scheme) approach. The scalability and convergence rate of the multigrid algorithm are examined on the SGI Origin 2000 and the Cray T3E. An argument is given which indicates that the asymptotic scalability of the multigrid algorithm should be similar to that of its underlying single grid smoothing scheme. For medium size problems involving several million grid points, near perfect scalability is obtained for the single grid algorithm, while only a slight drop-off in parallel efficiency is observed for the multigrid V- and W-cycles, using up to 128 processors on the SGI Origin 2000, and up to 512 processors on the Cray T3E. For a large problem using 25 million grid points, good scalability is observed for the multigrid algorithm using up to 1450 processors on a Cray T3E, even when the coarsest grid level contains fewer points than the total number of processors.
High Performance Parallel Multigrid Algorithms for Unstructured Grids
Frederickson, Paul O.
1996-01-01
We describe a high performance parallel multigrid algorithm for a rather general class of unstructured grid problems in two and three dimensions. The algorithm PUMG, for parallel unstructured multigrid, is related in structure to the parallel multigrid algorithm PSMG introduced by McBryan and Frederickson, for they both obtain a higher convergence rate through the use of multiple coarse grids. Another reason for the high convergence rate of PUMG is its smoother, an approximate inverse developed by Baumgardner and Frederickson.
Algorithms in Algebraic Geometry
Dickenstein, Alicia; Sommese, Andrew J
2008-01-01
In the last decade, there has been a burgeoning of activity in the design and implementation of algorithms for algebraic geometric computation. Some of these algorithms were originally designed for abstract algebraic geometry, but now are of interest for use in applications and some of these algorithms were originally designed for applications, but now are of interest for use in abstract algebraic geometry. The workshop on Algorithms in Algebraic Geometry that was held in the framework of the IMA Annual Program Year in Applications of Algebraic Geometry by the Institute for Mathematics and Its
Algebraic multigrid preconditioners for two-phase flow in porous media with phase transitions
Bui, Quan M.; Wang, Lu; Osei-Kuffuor, Daniel
2018-04-01
Multiphase flow is a critical process in a wide range of applications, including oil and gas recovery, carbon sequestration, and contaminant remediation. Numerical simulation of multiphase flow requires solving of a large, sparse linear system resulting from the discretization of the partial differential equations modeling the flow. In the case of multiphase multicomponent flow with miscible effect, this is a very challenging task. The problem becomes even more difficult if phase transitions are taken into account. A new approach to handle phase transitions is to formulate the system as a nonlinear complementarity problem (NCP). Unlike in the primary variable switching technique, the set of primary variables in this approach is fixed even when there is phase transition. Not only does this improve the robustness of the nonlinear solver, it opens up the possibility to use multigrid methods to solve the resulting linear system. The disadvantage of the complementarity approach, however, is that when a phase disappears, the linear system has the structure of a saddle point problem and becomes indefinite, and current algebraic multigrid (AMG) algorithms cannot be applied directly. In this study, we explore the effectiveness of a new multilevel strategy, based on the multigrid reduction technique, to deal with problems of this type. We demonstrate the effectiveness of the method through numerical results for the case of two-phase, two-component flow with phase appearance/disappearance. We also show that the strategy is efficient and scales optimally with problem size.
Non-Galerkin Coarse Grids for Algebraic Multigrid
Energy Technology Data Exchange (ETDEWEB)
Falgout, Robert D. [Lawrence Livermore National Lab. (LLNL), Livermore, CA (United States); Schroder, Jacob B. [Lawrence Livermore National Lab. (LLNL), Livermore, CA (United States)
2014-06-26
Algebraic multigrid (AMG) is a popular and effective solver for systems of linear equations that arise from discretized partial differential equations. And while AMG has been effectively implemented on large scale parallel machines, challenges remain, especially when moving to exascale. Particularly, stencil sizes (the number of nonzeros in a row) tend to increase further down in the coarse grid hierarchy, and this growth leads to more communication. Therefore, as problem size increases and the number of levels in the hierarchy grows, the overall efficiency of the parallel AMG method decreases, sometimes dramatically. This growth in stencil size is due to the standard Galerkin coarse grid operator, $P^T A P$, where $P$ is the prolongation (i.e., interpolation) operator. For example, the coarse grid stencil size for a simple three-dimensional (3D) seven-point finite differencing approximation to diffusion can increase into the thousands on present day machines, causing an associated increase in communication costs. We therefore consider algebraically truncating coarse grid stencils to obtain a non-Galerkin coarse grid. First, the sparsity pattern of the non-Galerkin coarse grid is determined by employing a heuristic minimal “safe” pattern together with strength-of-connection ideas. Second, the nonzero entries are determined by collapsing the stencils in the Galerkin operator using traditional AMG techniques. The result is a reduction in coarse grid stencil size, overall operator complexity, and parallel AMG solve phase times.
Mapping robust parallel multigrid algorithms to scalable memory architectures
Overman, Andrea; Vanrosendale, John
1993-01-01
The convergence rate of standard multigrid algorithms degenerates on problems with stretched grids or anisotropic operators. The usual cure for this is the use of line or plane relaxation. However, multigrid algorithms based on line and plane relaxation have limited and awkward parallelism and are quite difficult to map effectively to highly parallel architectures. Newer multigrid algorithms that overcome anisotropy through the use of multiple coarse grids rather than relaxation are better suited to massively parallel architectures because they require only simple point-relaxation smoothers. In this paper, we look at the parallel implementation of a V-cycle multiple semicoarsened grid (MSG) algorithm on distributed-memory architectures such as the Intel iPSC/860 and Paragon computers. The MSG algorithms provide two levels of parallelism: parallelism within the relaxation or interpolation on each grid and across the grids on each multigrid level. Both levels of parallelism must be exploited to map these algorithms effectively to parallel architectures. This paper describes a mapping of an MSG algorithm to distributed-memory architectures that demonstrates how both levels of parallelism can be exploited. The result is a robust and effective multigrid algorithm for distributed-memory machines.
Chen, Hui; Deng, Ju-Zhi; Yin, Min; Yin, Chang-Chun; Tang, Wen-Wu
2017-03-01
To speed up three-dimensional (3D) DC resistivity modeling, we present a new multigrid method, the aggregation-based algebraic multigrid method (AGMG). We first discretize the differential equation of the secondary potential field with mixed boundary conditions by using a seven-point finite-difference method to obtain a large sparse system of linear equations. Then, we introduce the theory behind the pairwise aggregation algorithms for AGMG and use the conjugate-gradient method with the V-cycle AGMG preconditioner (AGMG-CG) to solve the linear equations. We use typical geoelectrical models to test the proposed AGMG-CG method and compare the results with analytical solutions and the 3DDCXH algorithm for 3D DC modeling (3DDCXH). In addition, we apply the AGMG-CG method to different grid sizes and geoelectrical models and compare it to different iterative methods, such as ILU-BICGSTAB, ILU-GCR, and SSOR-CG. The AGMG-CG method yields nearly linearly decreasing errors, whereas the number of iterations increases slowly with increasing grid size. The AGMG-CG method is precise and converges fast, and thus can improve the computational efficiency in forward modeling of three-dimensional DC resistivity.
Trottenberg, Ulrich; Schuller, Anton
2000-01-01
Multigrid presents both an elementary introduction to multigrid methods for solving partial differential equations and a contemporary survey of advanced multigrid techniques and real-life applications.Multigrid methods are invaluable to researchers in scientific disciplines including physics, chemistry, meteorology, fluid and continuum mechanics, geology, biology, and all engineering disciplines. They are also becoming increasingly important in economics and financial mathematics.Readers are presented with an invaluable summary covering 25 years of practical experience acquired by the multigrid research group at the Germany National Research Center for Information Technology. The book presents both practical and theoretical points of view.* Covers the whole field of multigrid methods from its elements up to the most advanced applications* Style is essentially elementary but mathematically rigorous* No other book is so comprehensive and written for both practitioners and students
Asynchronous Task-Based Parallelization of Algebraic Multigrid
AlOnazi, Amani A.
2017-06-23
As processor clock rates become more dynamic and workloads become more adaptive, the vulnerability to global synchronization that already complicates programming for performance in today\\'s petascale environment will be exacerbated. Algebraic multigrid (AMG), the solver of choice in many large-scale PDE-based simulations, scales well in the weak sense, with fixed problem size per node, on tightly coupled systems when loads are well balanced and core performance is reliable. However, its strong scaling to many cores within a node is challenging. Reducing synchronization and increasing concurrency are vital adaptations of AMG to hybrid architectures. Recent communication-reducing improvements to classical additive AMG by Vassilevski and Yang improve concurrency and increase communication-computation overlap, while retaining convergence properties close to those of standard multiplicative AMG, but remain bulk synchronous.We extend the Vassilevski and Yang additive AMG to asynchronous task-based parallelism using a hybrid MPI+OmpSs (from the Barcelona Supercomputer Center) within a node, along with MPI for internode communications. We implement a tiling approach to decompose the grid hierarchy into parallel units within task containers. We compare against the MPI-only BoomerAMG and the Auxiliary-space Maxwell Solver (AMS) in the hypre library for the 3D Laplacian operator and the electromagnetic diffusion, respectively. In time to solution for a full solve an MPI-OmpSs hybrid improves over an all-MPI approach in strong scaling at full core count (32 threads per single Haswell node of the Cray XC40) and maintains this per node advantage as both weak scale to thousands of cores, with MPI between nodes.
Advanced Algebraic Multigrid Solvers for Subsurface Flow Simulation
Chen, Meng-Huo; Sun, Shuyu; Salama, Amgad
2015-01-01
and issues will be addressed and the corresponding remedies will be studied. As the multigrid methods are used as the linear solver, the simulator can be parallelized (although not trivial) and the high-resolution simulation become feasible, the ultimately
Energy Technology Data Exchange (ETDEWEB)
Kalchev, D. [Lawrence Livermore National Lab. (LLNL), Livermore, CA (United States); Ketelsen, C. [Lawrence Livermore National Lab. (LLNL), Livermore, CA (United States); Vassilevski, P. S. [Lawrence Livermore National Lab. (LLNL), Livermore, CA (United States)
2013-11-07
Our paper proposes an adaptive strategy for reusing a previously constructed coarse space by algebraic multigrid to construct a two-level solver for a problem with nearby characteristics. Furthermore, a main target application is the solution of the linear problems that appear throughout a sequence of Markov chain Monte Carlo simulations of subsurface flow with uncertain permeability field. We demonstrate the efficacy of the method with extensive set of numerical experiments.
Advanced Algebraic Multigrid Solvers for Subsurface Flow Simulation
Chen, Meng-Huo
2015-09-13
In this research we are particularly interested in extending the robustness of multigrid solvers to encounter complex systems related to subsurface reservoir applications for flow problems in porous media. In many cases, the step for solving the pressure filed in subsurface flow simulation becomes a bottleneck for the performance of the simulator. For solving large sparse linear system arising from MPFA discretization, we choose multigrid methods as the linear solver. The possible difficulties and issues will be addressed and the corresponding remedies will be studied. As the multigrid methods are used as the linear solver, the simulator can be parallelized (although not trivial) and the high-resolution simulation become feasible, the ultimately goal which we desire to achieve.
Energy Technology Data Exchange (ETDEWEB)
Druinsky, A; Ghysels, P; Li, XS; Marques, O; Williams, S; Barker, A; Kalchev, D; Vassilevski, P
2016-04-02
In this paper, we study the performance of a two-level algebraic-multigrid algorithm, with a focus on the impact of the coarse-grid solver on performance. We consider two algorithms for solving the coarse-space systems: the preconditioned conjugate gradient method and a new robust HSS-embedded low-rank sparse-factorization algorithm. Our test data comes from the SPE Comparative Solution Project for oil-reservoir simulations. We contrast the performance of our code on one 12-core socket of a Cray XC30 machine with performance on a 60-core Intel Xeon Phi coprocessor. To obtain top performance, we optimized the code to take full advantage of fine-grained parallelism and made it thread-friendly for high thread count. We also developed a bounds-and-bottlenecks performance model of the solver which we used to guide us through the optimization effort, and also carried out performance tuning in the solver’s large parameter space. Finally, as a result, significant speedups were obtained on both machines.
van der Vegt, Jacobus J.W.; Rhebergen, Sander
2011-01-01
The hp-Multigrid as Smoother algorithm (hp-MGS) for the solution of higher order accurate space-(time) discontinuous Galerkin discretizations of advection dominated flows is presented. This algorithm combines p-multigrid with h-multigrid at all p-levels, where the h-multigrid acts as smoother in the
Adaptive Multigrid Algorithm for the Lattice Wilson-Dirac Operator
International Nuclear Information System (INIS)
Babich, R.; Brower, R. C.; Rebbi, C.; Brannick, J.; Clark, M. A.; Manteuffel, T. A.; McCormick, S. F.; Osborn, J. C.
2010-01-01
We present an adaptive multigrid solver for application to the non-Hermitian Wilson-Dirac system of QCD. The key components leading to the success of our proposed algorithm are the use of an adaptive projection onto coarse grids that preserves the near null space of the system matrix together with a simplified form of the correction based on the so-called γ 5 -Hermitian symmetry of the Dirac operator. We demonstrate that the algorithm nearly eliminates critical slowing down in the chiral limit and that it has weak dependence on the lattice volume.
Asynchronous Task-Based Parallelization of Algebraic Multigrid
AlOnazi, Amani A.; Markomanolis, George S.; Keyes, David E.
2017-01-01
As processor clock rates become more dynamic and workloads become more adaptive, the vulnerability to global synchronization that already complicates programming for performance in today's petascale environment will be exacerbated. Algebraic
A Parallel Algebraic Multigrid Solver on Graphics Processing Units
Haase, Gundolf; Liebmann, Manfred; Douglas, Craig C.; Plank, Gernot
2010-01-01
-vector multiplication scheme underlying the PCG-AMG algorithm is presented for the many-core GPU architecture. A performance comparison of the parallel solver shows that a singe Nvidia Tesla C1060 GPU board delivers the performance of a sixteen node Infiniband cluster
Distance-two interpolation for parallel algebraic multigrid
International Nuclear Information System (INIS)
Sterck, H de; Falgout, R D; Nolting, J W; Yang, U M
2007-01-01
In this paper we study the use of long distance interpolation methods with the low complexity coarsening algorithm PMIS. AMG performance and scalability is compared for classical as well as long distance interpolation methods on parallel computers. It is shown that the increased interpolation accuracy largely restores the scalability of AMG convergence factors for PMIS-coarsened grids, and in combination with complexity reducing methods, such as interpolation truncation, one obtains a class of parallel AMG methods that enjoy excellent scalability properties on large parallel computers
Algebraic Algorithm Design and Local Search
National Research Council Canada - National Science Library
Graham, Robert
1996-01-01
.... Algebraic techniques have been applied successfully to algorithm synthesis by the use of algorithm theories and design tactics, an approach pioneered in the Kestrel Interactive Development System (KIDS...
Chen, Zhangxin; Ewing, Richard E.
1996-01-01
Multigrid algorithms for nonconforming and mixed finite element methods for second order elliptic problems on triangular and rectangular finite elements are considered. The construction of several coarse-to-fine intergrid transfer operators for nonconforming multigrid algorithms is discussed. The equivalence between the nonconforming and mixed finite element methods with and without projection of the coefficient of the differential problems into finite element spaces is described.
Adaptive Algebraic Multigrid for Finite Element Elliptic Equations with Random Coefficients
Energy Technology Data Exchange (ETDEWEB)
Kalchev, D
2012-04-02
This thesis presents a two-grid algorithm based on Smoothed Aggregation Spectral Element Agglomeration Algebraic Multigrid (SA-{rho}AMGe) combined with adaptation. The aim is to build an efficient solver for the linear systems arising from discretization of second-order elliptic partial differential equations (PDEs) with stochastic coefficients. Examples include PDEs that model subsurface flow with random permeability field. During a Markov Chain Monte Carlo (MCMC) simulation process, that draws PDE coefficient samples from a certain distribution, the PDE coefficients change, hence the resulting linear systems to be solved change. At every such step the system (discretized PDE) needs to be solved and the computed solution used to evaluate some functional(s) of interest that then determine if the coefficient sample is acceptable or not. The MCMC process is hence computationally intensive and requires the solvers used to be efficient and fast. This fact that at every step of MCMC the resulting linear system changes, makes an already existing solver built for the old problem perhaps not as efficient for the problem corresponding to the new sampled coefficient. This motivates the main goal of our study, namely, to adapt an already existing solver to handle the problem (with changed coefficient) with the objective to achieve this goal to be faster and more efficient than building a completely new solver from scratch. Our approach utilizes the local element matrices (for the problem with changed coefficients) to build local problems associated with constructed by the method agglomerated elements (a set of subdomains that cover the given computational domain). We solve a generalized eigenproblem for each set in a subspace spanned by the previous local coarse space (used for the old solver) and a vector, component of the error, that the old solver cannot handle. A portion of the spectrum of these local eigen-problems (corresponding to eigenvalues close to zero) form the
Robust Algebraic Multilevel Methods and Algorithms
Kraus, Johannes
2009-01-01
This book deals with algorithms for the solution of linear systems of algebraic equations with large-scale sparse matrices, with a focus on problems that are obtained after discretization of partial differential equations using finite element methods. Provides a systematic presentation of the recent advances in robust algebraic multilevel methods. Can be used for advanced courses on the topic.
A multigrid algorithm for the cell-centered finite difference scheme
Ewing, Richard E.; Shen, Jian
1993-01-01
In this article, we discuss a non-variational V-cycle multigrid algorithm based on the cell-centered finite difference scheme for solving a second-order elliptic problem with discontinuous coefficients. Due to the poor approximation property of piecewise constant spaces and the non-variational nature of our scheme, one step of symmetric linear smoothing in our V-cycle multigrid scheme may fail to be a contraction. Again, because of the simple structure of the piecewise constant spaces, prolongation and restriction are trivial; we save significant computation time with very promising computational results.
A parallel version of a multigrid algorithm for isotropic transport equations
International Nuclear Information System (INIS)
Manteuffel, T.; McCormick, S.; Yang, G.; Morel, J.; Oliveira, S.
1994-01-01
The focus of this paper is on a parallel algorithm for solving the transport equations in a slab geometry using multigrid. The spatial discretization scheme used is a finite element method called the modified linear discontinuous (MLD) scheme. The MLD scheme represents a lumped version of the standard linear discontinuous (LD) scheme. The parallel algorithm was implemented on the Connection Machine 2 (CM2). Convergence rates and timings for this algorithm on the CM2 and Cray-YMP are shown
International Nuclear Information System (INIS)
Barry, J.M.; Pollard, J.P.
1986-11-01
A FORTRAN subroutine MLTGRD is provided to solve efficiently the large systems of linear equations arising from a five-point finite difference discretisation of some elliptic partial differential equations. MLTGRD is a multigrid algorithm which provides multiplicative correction to iterative solution estimates from successively reduced systems of linear equations. It uses the method of implicit non-stationary iteration for all grid levels
1980-10-01
solving (1.3); PFAS combines the concepts of multigrid algorithms with those of projected SOR. In Section 3, we discuss the implementation of PFAS, and...numerique de la torsion elasto- plastique d’une barre cylindrique. In Approximation et Methodes Iteratives de Resolution d’Inequations Variationelles et
Self-correcting Multigrid Solver
International Nuclear Information System (INIS)
Lewandowski, Jerome L.V.
2004-01-01
A new multigrid algorithm based on the method of self-correction for the solution of elliptic problems is described. The method exploits information contained in the residual to dynamically modify the source term (right-hand side) of the elliptic problem. It is shown that the self-correcting solver is more efficient at damping the short wavelength modes of the algebraic error than its standard equivalent. When used in conjunction with a multigrid method, the resulting solver displays an improved convergence rate with no additional computational work
Koldan, Jelena; Puzyrev, Vladimir; de la Puente, Josep; Houzeaux, Guillaume; Cela, José María
2014-06-01
We present an elaborate preconditioning scheme for Krylov subspace methods which has been developed to improve the performance and reduce the execution time of parallel node-based finite-element (FE) solvers for 3-D electromagnetic (EM) numerical modelling in exploration geophysics. This new preconditioner is based on algebraic multigrid (AMG) that uses different basic relaxation methods, such as Jacobi, symmetric successive over-relaxation (SSOR) and Gauss-Seidel, as smoothers and the wave front algorithm to create groups, which are used for a coarse-level generation. We have implemented and tested this new preconditioner within our parallel nodal FE solver for 3-D forward problems in EM induction geophysics. We have performed series of experiments for several models with different conductivity structures and characteristics to test the performance of our AMG preconditioning technique when combined with biconjugate gradient stabilized method. The results have shown that, the more challenging the problem is in terms of conductivity contrasts, ratio between the sizes of grid elements and/or frequency, the more benefit is obtained by using this preconditioner. Compared to other preconditioning schemes, such as diagonal, SSOR and truncated approximate inverse, the AMG preconditioner greatly improves the convergence of the iterative solver for all tested models. Also, when it comes to cases in which other preconditioners succeed to converge to a desired precision, AMG is able to considerably reduce the total execution time of the forward-problem code-up to an order of magnitude. Furthermore, the tests have confirmed that our AMG scheme ensures grid-independent rate of convergence, as well as improvement in convergence regardless of how big local mesh refinements are. In addition, AMG is designed to be a black-box preconditioner, which makes it easy to use and combine with different iterative methods. Finally, it has proved to be very practical and efficient in the
An algorithm to construct the basic algebra of a skew group algebra
Horobeţ, E.
2016-01-01
We give an algorithm for the computation of the basic algebra Morita equivalent to a skew group algebra of a path algebra by obtaining formulas for the number of vertices and arrows of the new quiver Qb. We apply this algorithm to compute the basic algebra corresponding to all simple quaternion
Optimal multigrid algorithms for the massive Gaussian model and path integrals
International Nuclear Information System (INIS)
Brandt, A.; Galun, M.
1996-01-01
Multigrid algorithms are presented which, in addition to eliminating the critical slowing down, can also eliminate the open-quotes volume factorclose quotes. The elimination of the volume factor removes the need to produce many independent fine-grid configurations for averaging out their statistical deviations, by averaging over the many samples produced on coarse grids during the multigrid cycle. Thermodynamic limits of observables can be calculated to relative accuracy var-epsilon r in just O(var-epsilon r -2 ) computer operations, where var-epsilon r is the error relative to the standard deviation of the observable. In this paper, we describe in detail the calculation of the susceptibility in the one-dimensional massive Gaussian model, which is also a simple example of path integrals. Numerical experiments show that the susceptibility can be calculated to relative accuracy var-epsilon r in about 8 var-epsilon r -2 random number generations, independent of the mass size
DEFF Research Database (Denmark)
Christensen, Max la Cour; Villa, Umberto; Engsig-Karup, Allan Peter
2017-01-01
associated with non-planar interfaces between agglomerates, the coarse velocity space has guaranteed approximation properties. The employed AMGe technique provides coarse spaces with desirable local mass conservation and stability properties analogous to the original pair of Raviart-Thomas and piecewise......We study the application of a finite element numerical upscaling technique to the incompressible two-phase porous media total velocity formulation. Specifically, an element agglomeration based Algebraic Multigrid (AMGe) technique with improved approximation proper ties [37] is used, for the first...... discontinuous polynomial spaces, resulting in strong mass conservation for the upscaled systems. Due to the guaranteed approximation properties and the generic nature of the AMGe method, recursive multilevel upscaling is automatically obtained. Furthermore, this technique works for both structured...
Gonzalez-Vega, Laureano
1999-01-01
Using a Computer Algebra System (CAS) to help with the teaching of an elementary course in linear algebra can be one way to introduce computer algebra, numerical analysis, data structures, and algorithms. Highlights the advantages and disadvantages of this approach to the teaching of linear algebra. (Author/MM)
Parallel algorithms for numerical linear algebra
van der Vorst, H
1990-01-01
This is the first in a new series of books presenting research results and developments concerning the theory and applications of parallel computers, including vector, pipeline, array, fifth/future generation computers, and neural computers.All aspects of high-speed computing fall within the scope of the series, e.g. algorithm design, applications, software engineering, networking, taxonomy, models and architectural trends, performance, peripheral devices.Papers in Volume One cover the main streams of parallel linear algebra: systolic array algorithms, message-passing systems, algorithms for p
New multigrid solver advances in TOPS
International Nuclear Information System (INIS)
Falgout, R D; Brannick, J; Brezina, M; Manteuffel, T; McCormick, S
2005-01-01
In this paper, we highlight new multigrid solver advances in the Terascale Optimal PDE Simulations (TOPS) project in the Scientific Discovery Through Advanced Computing (SciDAC) program. We discuss two new algebraic multigrid (AMG) developments in TOPS: the adaptive smoothed aggregation method (αSA) and a coarse-grid selection algorithm based on compatible relaxation (CR). The αSA method is showing promising results in initial studies for Quantum Chromodynamics (QCD) applications. The CR method has the potential to greatly improve the applicability of AMG
A Multigrid Algorithm for an Elliptic Problem with a Perturbed Boundary Condition
Bonito, Andrea; Pasciak, Joseph E.
2013-01-01
We discuss the preconditioning of systems coupling elliptic operators in Ω⊂Rd, d=2,3, with elliptic operators defined on hypersurfaces. These systems arise naturally when physical phenomena are affected by geometric boundary forces, such as the evolution of liquid drops subject to surface tension. The resulting operators are sums of interior and boundary terms weighted by parameters. We investigate the behavior of multigrid algorithms suited to this context and demonstrate numerical results which suggest uniform preconditioning bounds that are level and parameter independent.
Bonito, Andrea
2012-09-01
We design and analyze variational and non-variational multigrid algorithms for the Laplace-Beltrami operator on a smooth and closed surface. In both cases, a uniform convergence for the V -cycle algorithm is obtained provided the surface geometry is captured well enough by the coarsest grid. The main argument hinges on a perturbation analysis from an auxiliary variational algorithm defined directly on the smooth surface. In addition, the vanishing mean value constraint is imposed on each level, thereby avoiding singular quadratic forms without adding additional computational cost. Numerical results supporting our analysis are reported. In particular, the algorithms perform well even when applied to surfaces with a large aspect ratio. © 2011 American Mathematical Society.
Homogeneous Buchberger algorithms and Sullivant's computational commutative algebra challenge
DEFF Research Database (Denmark)
Lauritzen, Niels
2005-01-01
We give a variant of the homogeneous Buchberger algorithm for positively graded lattice ideals. Using this algorithm we solve the Sullivant computational commutative algebra challenge.......We give a variant of the homogeneous Buchberger algorithm for positively graded lattice ideals. Using this algorithm we solve the Sullivant computational commutative algebra challenge....
Algorithmic algebraic geometry and flux vacua
International Nuclear Information System (INIS)
Gray, James; He Yanghui; Lukas, Andre
2006-01-01
We develop a new and efficient method to systematically analyse four dimensional effective supergravities which descend from flux compactifications. The issue of finding vacua of such systems, both supersymmetric and non-supersymmetric, is mapped into a problem in computational algebraic geometry. Using recent developments in computer algebra, the problem can then be rapidly dealt with in a completely algorithmic fashion. Two main results are (1) a procedure for calculating constraints which the flux parameters must satisfy in these models if any given type of vacuum is to exist; (2) a stepwise process for finding all of the isolated vacua of such systems and their physical properties. We illustrate our discussion with several concrete examples, some of which have eluded conventional methods so far
Optical linear algebra processors - Architectures and algorithms
Casasent, David
1986-01-01
Attention is given to the component design and optical configuration features of a generic optical linear algebra processor (OLAP) architecture, as well as the large number of OLAP architectures, number representations, algorithms and applications encountered in current literature. Number-representation issues associated with bipolar and complex-valued data representations, high-accuracy (including floating point) performance, and the base or radix to be employed, are discussed, together with case studies on a space-integrating frequency-multiplexed architecture and a hybrid space-integrating and time-integrating multichannel architecture.
Layer-oriented multigrid wavefront reconstruction algorithms for multi-conjugate adaptive optics
Gilles, Luc; Ellerbroek, Brent L.; Vogel, Curtis R.
2003-02-01
Multi-conjugate adaptive optics (MCAO) systems with 104-105 degrees of freedom have been proposed for future giant telescopes. Using standard matrix methods to compute, optimize, and implement wavefront control algorithms for these systems is impractical, since the number of calculations required to compute and apply the reconstruction matrix scales respectively with the cube and the square of the number of AO degrees of freedom. In this paper, we develop an iterative sparse matrix implementation of minimum variance wavefront reconstruction for telescope diameters up to 32m with more than 104 actuators. The basic approach is the preconditioned conjugate gradient method, using a multigrid preconditioner incorporating a layer-oriented (block) symmetric Gauss-Seidel iterative smoothing operator. We present open-loop numerical simulation results to illustrate algorithm convergence.
van der Vegt, Jacobus J.W.; Rhebergen, Sander
2012-01-01
Using a detailed multilevel analysis of the complete hp-Multigrid as Smoother algorithm accurate predictions are obtained of the spectral radius and operator norms of the multigrid error transformation operator. This multilevel analysis is used to optimize the coefficients in the semi-implicit
Institute of Scientific and Technical Information of China (English)
WANG ShunJin; ZHANG Hua
2007-01-01
Based on the exact analytical solution of ordinary differential equations,a truncation of the Taylor series of the exact solution to the Nth order leads to the Nth order algebraic dynamics algorithm.A detailed numerical comparison is presented with Runge-Kutta algorithm and symplectic geometric algorithm for 12 test models.The results show that the algebraic dynamics algorithm can better preserve both geometrical and dynamical fidelity of a dynamical system at a controllable precision,and it can solve the problem of algorithm-induced dissipation for the Runge-Kutta algorithm and the problem of algorithm-induced phase shift for the symplectic geometric algorithm.
Institute of Scientific and Technical Information of China (English)
2007-01-01
Based on the exact analytical solution of ordinary differential equations, a truncation of the Taylor series of the exact solution to the Nth order leads to the Nth order algebraic dynamics algorithm. A detailed numerical comparison is presented with Runge-Kutta algorithm and symplectic geometric algorithm for 12 test models. The results show that the algebraic dynamics algorithm can better preserve both geometrical and dynamical fidelity of a dynamical system at a controllable precision, and it can solve the problem of algorithm-induced dissipation for the Runge-Kutta algorithm and the problem of algorithm-induced phase shift for the symplectic geometric algorithm.
MAPCUMBA: A fast iterative multi-grid map-making algorithm for CMB experiments
Doré, O.; Teyssier, R.; Bouchet, F. R.; Vibert, D.; Prunet, S.
2001-07-01
The data analysis of current Cosmic Microwave Background (CMB) experiments like BOOMERanG or MAXIMA poses severe challenges which already stretch the limits of current (super-) computer capabilities, if brute force methods are used. In this paper we present a practical solution for the optimal map making problem which can be used directly for next generation CMB experiments like ARCHEOPS and TopHat, and can probably be extended relatively easily to the full PLANCK case. This solution is based on an iterative multi-grid Jacobi algorithm which is both fast and memory sparing. Indeed, if there are Ntod data points along the one dimensional timeline to analyse, the number of operations is of O (Ntod \\ln Ntod) and the memory requirement is O (Ntod). Timing and accuracy issues have been analysed on simulated ARCHEOPS and TopHat data, and we discuss as well the issue of the joint evaluation of the signal and noise statistical properties.
Construction Example for Algebra System Using Harmony Search Algorithm
Directory of Open Access Journals (Sweden)
FangAn Deng
2015-01-01
Full Text Available The construction example of algebra system is to verify the existence of a complex algebra system, and it is a NP-hard problem. In this paper, to solve this kind of problems, firstly, a mathematical optimization model for construction example of algebra system is established. Secondly, an improved harmony search algorithm based on NGHS algorithm (INGHS is proposed to find as more solutions as possible for the optimization model; in the proposed INGHS algorithm, to achieve the balance between exploration power and exploitation power in the search process, a global best strategy and parameters dynamic adjustment method are present. Finally, nine construction examples of algebra system are used to evaluate the optimization model and performance of INGHS. The experimental results show that the proposed algorithm has strong performance for solving complex construction example problems of algebra system.
Institute of Scientific and Technical Information of China (English)
WANG; Shunjin; ZHANG; Hua
2006-01-01
The problem of preserving fidelity in numerical computation of nonlinear ordinary differential equations is studied in terms of preserving local differential structure and approximating global integration structure of the dynamical system.The ordinary differential equations are lifted to the corresponding partial differential equations in the framework of algebraic dynamics,and a new algorithm-algebraic dynamics algorithm is proposed based on the exact analytical solutions of the ordinary differential equations by the algebraic dynamics method.In the new algorithm,the time evolution of the ordinary differential system is described locally by the time translation operator and globally by the time evolution operator.The exact analytical piece-like solution of the ordinary differential equations is expressd in terms of Taylor series with a local convergent radius,and its finite order truncation leads to the new numerical algorithm with a controllable precision better than Runge Kutta Algorithm and Symplectic Geometric Algorithm.
Performance Analysis of a Decoding Algorithm for Algebraic Geometry Codes
DEFF Research Database (Denmark)
Jensen, Helge Elbrønd; Nielsen, Rasmus Refslund; Høholdt, Tom
1998-01-01
We analyse the known decoding algorithms for algebraic geometry codes in the case where the number of errors is greater than or equal to [(dFR-1)/2]+1, where dFR is the Feng-Rao distance......We analyse the known decoding algorithms for algebraic geometry codes in the case where the number of errors is greater than or equal to [(dFR-1)/2]+1, where dFR is the Feng-Rao distance...
An implicit multigrid algorithm for computing hypersonic, chemically reacting viscous flows
International Nuclear Information System (INIS)
Edwards, J.R.
1996-01-01
An implicit algorithm for computing viscous flows in chemical nonequilibrium is presented. Emphasis is placed on the numerical efficiency of the time integration scheme, both in terms of periteration workload and overall convergence rate. In this context, several techniques are introduced, including a stable, O(m 2 ) approximate factorization of the chemical source Jacobian and implementations of V-cycle and filtered multigrid acceleration methods. A five species-seventeen reaction air model is used to calculate hypersonic viscous flow over a cylinder at conditions corresponding to flight at 5 km/s, 60 km altitude and at 11.36 km/s, 76.42 km altitude. Inviscid calculations using an eleven-species reaction mechanism including ionization are presented for a case involving 11.37 km/s flow at an altitude of 84.6 km. Comparisons among various options for the implicit treatment of the chemical source terms and among different multilevel approaches for convergence acceleration are presented for all simulations
International Nuclear Information System (INIS)
Wu, Vincent W.C.; Tse, Teddy K.H.; Ho, Cola L.M.; Yeung, Eric C.Y.
2013-01-01
Monte Carlo (MC) simulation is currently the most accurate dose calculation algorithm in radiotherapy planning but requires relatively long processing time. Faster model-based algorithms such as the anisotropic analytical algorithm (AAA) by the Eclipse treatment planning system and multigrid superposition (MGS) by the XiO treatment planning system are 2 commonly used algorithms. This study compared AAA and MGS against MC, as the gold standard, on brain, nasopharynx, lung, and prostate cancer patients. Computed tomography of 6 patients of each cancer type was used. The same hypothetical treatment plan using the same machine and treatment prescription was computed for each case by each planning system using their respective dose calculation algorithm. The doses at reference points including (1) soft tissues only, (2) bones only, (3) air cavities only, (4) soft tissue-bone boundary (Soft/Bone), (5) soft tissue-air boundary (Soft/Air), and (6) bone-air boundary (Bone/Air), were measured and compared using the mean absolute percentage error (MAPE), which was a function of the percentage dose deviations from MC. Besides, the computation time of each treatment plan was recorded and compared. The MAPEs of MGS were significantly lower than AAA in all types of cancers (p<0.001). With regards to body density combinations, the MAPE of AAA ranged from 1.8% (soft tissue) to 4.9% (Bone/Air), whereas that of MGS from 1.6% (air cavities) to 2.9% (Soft/Bone). The MAPEs of MGS (2.6%±2.1) were significantly lower than that of AAA (3.7%±2.5) in all tissue density combinations (p<0.001). The mean computation time of AAA for all treatment plans was significantly lower than that of the MGS (p<0.001). Both AAA and MGS algorithms demonstrated dose deviations of less than 4.0% in most clinical cases and their performance was better in homogeneous tissues than at tissue boundaries. In general, MGS demonstrated relatively smaller dose deviations than AAA but required longer computation time
Applied algebra codes, ciphers and discrete algorithms
Hardy, Darel W; Walker, Carol L
2009-01-01
This book attempts to show the power of algebra in a relatively simple setting.-Mathematical Reviews, 2010… The book supports learning by doing. In each section we can find many examples which clarify the mathematics introduced in the section and each section is followed by a series of exercises of which approximately half are solved in the end of the book. Additional the book comes with a CD-ROM containing an interactive version of the book powered by the computer algebra system Scientific Notebook. … the mathematics in the book are developed as needed and the focus of the book lies clearly o
Institute of Scientific and Technical Information of China (English)
2008-01-01
Using functional derivative technique in quantum field theory, the algebraic dy-namics approach for solution of ordinary differential evolution equations was gen-eralized to treat partial differential evolution equations. The partial differential evo-lution equations were lifted to the corresponding functional partial differential equations in functional space by introducing the time translation operator. The functional partial differential evolution equations were solved by algebraic dynam-ics. The algebraic dynamics solutions are analytical in Taylor series in terms of both initial functions and time. Based on the exact analytical solutions, a new nu-merical algorithm—algebraic dynamics algorithm was proposed for partial differ-ential evolution equations. The difficulty of and the way out for the algorithm were discussed. The application of the approach to and computer numerical experi-ments on the nonlinear Burgers equation and meteorological advection equation indicate that the algebraic dynamics approach and algebraic dynamics algorithm are effective to the solution of nonlinear partial differential evolution equations both analytically and numerically.
Rasthofer, U.; Wall, W. A.; Gravemeier, V.
2018-04-01
A novel and comprehensive computational method, referred to as the eXtended Algebraic Variational Multiscale-Multigrid-Multifractal Method (XAVM4), is proposed for large-eddy simulation of the particularly challenging problem of turbulent two-phase flow. The XAVM4 involves multifractal subgrid-scale modeling as well as a Nitsche-type extended finite element method as an approach for two-phase flow. The application of an advanced structural subgrid-scale modeling approach in conjunction with a sharp representation of the discontinuities at the interface between two bulk fluids promise high-fidelity large-eddy simulation of turbulent two-phase flow. The high potential of the XAVM4 is demonstrated for large-eddy simulation of turbulent two-phase bubbly channel flow, that is, turbulent channel flow carrying a single large bubble of the size of the channel half-width in this particular application.
High performance linear algebra algorithms: An introduction
DEFF Research Database (Denmark)
Gustavson, F.G.; Wasniewski, Jerzy
2006-01-01
his Mini-Symposium consisted of two back to back sessions, each consisting of five presentations, held on the afternoon of Monday, June 21, 2004. A major theme of both sessions was novel data structures for the matrices of dense linear algebra, DLA. Talks one to four of session one all centered...
Algorithmic and experimental methods in algebra, geometry, and number theory
Decker, Wolfram; Malle, Gunter
2017-01-01
This book presents state-of-the-art research and survey articles that highlight work done within the Priority Program SPP 1489 “Algorithmic and Experimental Methods in Algebra, Geometry and Number Theory”, which was established and generously supported by the German Research Foundation (DFG) from 2010 to 2016. The goal of the program was to substantially advance algorithmic and experimental methods in the aforementioned disciplines, to combine the different methods where necessary, and to apply them to central questions in theory and practice. Of particular concern was the further development of freely available open source computer algebra systems and their interaction in order to create powerful new computational tools that transcend the boundaries of the individual disciplines involved. The book covers a broad range of topics addressing the design and theoretical foundations, implementation and the successful application of algebraic algorithms in order to solve mathematical research problems. It off...
An evaluation of parallel multigrid as a solver and a preconditioner for singular perturbed problems
Energy Technology Data Exchange (ETDEWEB)
Oosterlee, C.W. [Inst. for Algorithms and Scientific Computing, Sankt Augustin (Germany); Washio, T. [C& C Research Lab., Sankt Augustin (Germany)
1996-12-31
In this paper we try to achieve h-independent convergence with preconditioned GMRES and BiCGSTAB for 2D singular perturbed equations. Three recently developed multigrid methods are adopted as a preconditioner. They are also used as solution methods in order to compare the performance of the methods as solvers and as preconditioners. Two of the multigrid methods differ only in the transfer operators. One uses standard matrix- dependent prolongation operators from. The second uses {open_quotes}upwind{close_quotes} prolongation operators, developed. Both employ the Galerkin coarse grid approximation and an alternating zebra line Gauss-Seidel smoother. The third method is based on the block LU decomposition of a matrix and on an approximate Schur complement. This multigrid variant is presented in. All three multigrid algorithms are algebraic methods.
Algorithmic Algebraic Combinatorics and Gröbner Bases
Klin, Mikhail; Jurisic, Aleksandar
2009-01-01
This collection of tutorial and research papers introduces readers to diverse areas of modern pure and applied algebraic combinatorics and finite geometries with a special emphasis on algorithmic aspects and the use of the theory of Grobner bases. Topics covered include coherent configurations, association schemes, permutation groups, Latin squares, the Jacobian conjecture, mathematical chemistry, extremal combinatorics, coding theory, designs, etc. Special attention is paid to the description of innovative practical algorithms and their implementation in software packages such as GAP and MAGM
Multigrid Methods for Fully Implicit Oil Reservoir Simulation
Molenaar, J.
1996-01-01
In this paper we consider the simultaneous flow of oil and water in reservoir rock. This displacement process is modeled by two basic equations: the material balance or continuity equations and the equation of motion (Darcy's law). For the numerical solution of this system of nonlinear partial differential equations there are two approaches: the fully implicit or simultaneous solution method and the sequential solution method. In the sequential solution method the system of partial differential equations is manipulated to give an elliptic pressure equation and a hyperbolic (or parabolic) saturation equation. In the IMPES approach the pressure equation is first solved, using values for the saturation from the previous time level. Next the saturations are updated by some explicit time stepping method; this implies that the method is only conditionally stable. For the numerical solution of the linear, elliptic pressure equation multigrid methods have become an accepted technique. On the other hand, the fully implicit method is unconditionally stable, but it has the disadvantage that in every time step a large system of nonlinear algebraic equations has to be solved. The most time-consuming part of any fully implicit reservoir simulator is the solution of this large system of equations. Usually this is done by Newton's method. The resulting systems of linear equations are then either solved by a direct method or by some conjugate gradient type method. In this paper we consider the possibility of applying multigrid methods for the iterative solution of the systems of nonlinear equations. There are two ways of using multigrid for this job: either we use a nonlinear multigrid method or we use a linear multigrid method to deal with the linear systems that arise in Newton's method. So far only a few authors have reported on the use of multigrid methods for fully implicit simulations. Two-level FAS algorithm is presented for the black-oil equations, and linear multigrid for
Algorithm for solving polynomial algebraic Riccati equations and its application
Czech Academy of Sciences Publication Activity Database
Augusta, Petr; Augustová, Petra
2012-01-01
Roč. 1, č. 4 (2012), s. 237-242 ISSN 2223-7038 R&D Projects: GA ČR GPP103/12/P494 Institutional support: RVO:67985556 Keywords : Numerical algorithms * algebraic Riccati equation * spatially distributed systems * optimal control Subject RIV: BC - Control Systems Theory http://lib.physcon.ru/doc?id=8b4876d6a57d
MultiAspect Graphs: Algebraic Representation and Algorithms
Directory of Open Access Journals (Sweden)
Klaus Wehmuth
2016-12-01
Full Text Available We present the algebraic representation and basic algorithms for MultiAspect Graphs (MAGs. A MAG is a structure capable of representing multilayer and time-varying networks, as well as higher-order networks, while also having the property of being isomorphic to a directed graph. In particular, we show that, as a consequence of the properties associated with the MAG structure, a MAG can be represented in matrix form. Moreover, we also show that any possible MAG function (algorithm can be obtained from this matrix-based representation. This is an important theoretical result since it paves the way for adapting well-known graph algorithms for application in MAGs. We present a set of basic MAG algorithms, constructed from well-known graph algorithms, such as degree computing, Breadth First Search (BFS, and Depth First Search (DFS. These algorithms adapted to the MAG context can be used as primitives for building other more sophisticated MAG algorithms. Therefore, such examples can be seen as guidelines on how to properly derive MAG algorithms from basic algorithms on directed graphs. We also make available Python implementations of all the algorithms presented in this paper.
Acoustooptic linear algebra processors - Architectures, algorithms, and applications
Casasent, D.
1984-01-01
Architectures, algorithms, and applications for systolic processors are described with attention to the realization of parallel algorithms on various optical systolic array processors. Systolic processors for matrices with special structure and matrices of general structure, and the realization of matrix-vector, matrix-matrix, and triple-matrix products and such architectures are described. Parallel algorithms for direct and indirect solutions to systems of linear algebraic equations and their implementation on optical systolic processors are detailed with attention to the pipelining and flow of data and operations. Parallel algorithms and their optical realization for LU and QR matrix decomposition are specifically detailed. These represent the fundamental operations necessary in the implementation of least squares, eigenvalue, and SVD solutions. Specific applications (e.g., the solution of partial differential equations, adaptive noise cancellation, and optimal control) are described to typify the use of matrix processors in modern advanced signal processing.
ADART: an adaptive algebraic reconstruction algorithm for discrete tomography.
Maestre-Deusto, F Javier; Scavello, Giovanni; Pizarro, Joaquín; Galindo, Pedro L
2011-08-01
In this paper we suggest an algorithm based on the Discrete Algebraic Reconstruction Technique (DART) which is capable of computing high quality reconstructions from substantially fewer projections than required for conventional continuous tomography. Adaptive DART (ADART) goes a step further than DART on the reduction of the number of unknowns of the associated linear system achieving a significant reduction in the pixel error rate of reconstructed objects. The proposed methodology automatically adapts the border definition criterion at each iteration, resulting in a reduction of the number of pixels belonging to the border, and consequently of the number of unknowns in the general algebraic reconstruction linear system to be solved, being this reduction specially important at the final stage of the iterative process. Experimental results show that reconstruction errors are considerably reduced using ADART when compared to original DART, both in clean and noisy environments.
An Algorithm for Isolating the Real Solutions of Piecewise Algebraic Curves
Directory of Open Access Journals (Sweden)
Jinming Wu
2011-01-01
to compute the real solutions of two piecewise algebraic curves. It is primarily based on the Krawczyk-Moore iterative algorithm and good initial iterative interval searching algorithm. The proposed algorithm is relatively easy to implement.
Multigrid methods for partial differential equations - a short introduction
International Nuclear Information System (INIS)
Linden, J.; Stueben, K.
1993-01-01
These notes summarize the multigrid methods and emphasis is laid on the algorithmic concepts of multigrid for solving linear and non-linear partial differential equations. In this paper there is brief description of the basic structure of multigrid methods. Detailed introduction is also contained with applications to VLSI process simulation. (A.B.)
Advanced computer algebra algorithms for the expansion of Feynman integrals
International Nuclear Information System (INIS)
Ablinger, Jakob; Round, Mark; Schneider, Carsten
2012-10-01
Two-point Feynman parameter integrals, with at most one mass and containing local operator insertions in 4+ε-dimensional Minkowski space, can be transformed to multi-integrals or multi-sums over hyperexponential and/or hypergeometric functions depending on a discrete parameter n. Given such a specific representation, we utilize an enhanced version of the multivariate Almkvist-Zeilberger algorithm (for multi-integrals) and a common summation framework of the holonomic and difference field approach (for multi-sums) to calculate recurrence relations in n. Finally, solving the recurrence we can decide efficiently if the first coefficients of the Laurent series expansion of a given Feynman integral can be expressed in terms of indefinite nested sums and products; if yes, the all n solution is returned in compact representations, i.e., no algebraic relations exist among the occurring sums and products.
Advanced computer algebra algorithms for the expansion of Feynman integrals
Energy Technology Data Exchange (ETDEWEB)
Ablinger, Jakob; Round, Mark; Schneider, Carsten [Johannes Kepler Univ., Linz (Austria). Research Inst. for Symbolic Computation; Bluemlein, Johannes [Deutsches Elektronen-Synchrotron (DESY), Zeuthen (Germany)
2012-10-15
Two-point Feynman parameter integrals, with at most one mass and containing local operator insertions in 4+{epsilon}-dimensional Minkowski space, can be transformed to multi-integrals or multi-sums over hyperexponential and/or hypergeometric functions depending on a discrete parameter n. Given such a specific representation, we utilize an enhanced version of the multivariate Almkvist-Zeilberger algorithm (for multi-integrals) and a common summation framework of the holonomic and difference field approach (for multi-sums) to calculate recurrence relations in n. Finally, solving the recurrence we can decide efficiently if the first coefficients of the Laurent series expansion of a given Feynman integral can be expressed in terms of indefinite nested sums and products; if yes, the all n solution is returned in compact representations, i.e., no algebraic relations exist among the occurring sums and products.
Bonito, Andrea; Pasciak, Joseph E.
2012-01-01
is captured well enough by the coarsest grid. The main argument hinges on a perturbation analysis from an auxiliary variational algorithm defined directly on the smooth surface. In addition, the vanishing mean value constraint is imposed on each level, thereby
Multigrid methods in structural mechanics
Raju, I. S.; Bigelow, C. A.; Taasan, S.; Hussaini, M. Y.
1986-01-01
Although the application of multigrid methods to the equations of elasticity has been suggested, few such applications have been reported in the literature. In the present work, multigrid techniques are applied to the finite element analysis of a simply supported Bernoulli-Euler beam, and various aspects of the multigrid algorithm are studied and explained in detail. In this study, six grid levels were used to model half the beam. With linear prolongation and sequential ordering, the multigrid algorithm yielded results which were of machine accuracy with work equivalent to 200 standard Gauss-Seidel iterations on the fine grid. Also with linear prolongation and sequential ordering, the V(1,n) cycle with n greater than 2 yielded better convergence rates than the V(n,1) cycle. The restriction and prolongation operators were derived based on energy principles. Conserving energy during the inter-grid transfers required that the prolongation operator be the transpose of the restriction operator, and led to improved convergence rates. With energy-conserving prolongation and sequential ordering, the multigrid algorithm yielded results of machine accuracy with a work equivalent to 45 Gauss-Seidel iterations on the fine grid. The red-black ordering of relaxations yielded solutions of machine accuracy in a single V(1,1) cycle, which required work equivalent to about 4 iterations on the finest grid level.
Cox, David A; O'Shea, Donal
2015-01-01
This text covers topics in algebraic geometry and commutative algebra with a strong perspective toward practical and computational aspects. The first four chapters form the core of the book. A comprehensive chart in the preface illustrates a variety of ways to proceed with the material once these chapters are covered. In addition to the fundamentals of algebraic geometry—the elimination theorem, the extension theorem, the closure theorem, and the Nullstellensatz—this new edition incorporates several substantial changes, all of which are listed in the Preface. The largest revision incorporates a new chapter (ten), which presents some of the essentials of progress made over the last decades in computing Gröbner bases. The book also includes current computer algebra material in Appendix C and updated independent projects (Appendix D). The book may serve as a first or second course in undergraduate abstract algebra and, with some supplementation perhaps, for beginning graduate level courses in algebraic geom...
A NetCDF version of the two-dimensional energy balance model based on the full multigrid algorithm
Zhuang, Kelin; North, Gerald R.; Stevens, Mark J.
A NetCDF version of the two-dimensional energy balance model based on the full multigrid method in Fortran is introduced for both pedagogical and research purposes. Based on the land-sea-ice distribution, orbital elements, greenhouse gases concentration, and albedo, the code calculates the global seasonal surface temperature. A step-by-step guide with examples is provided for practice.
Dinar, N.
1978-01-01
Several aspects of multigrid methods are briefly described. The main subjects include the development of very efficient multigrid algorithms for systems of elliptic equations (Cauchy-Riemann, Stokes, Navier-Stokes), as well as the development of control and prediction tools (based on local mode Fourier analysis), used to analyze, check and improve these algorithms. Preliminary research on multigrid algorithms for time dependent parabolic equations is also described. Improvements in existing multigrid processes and algorithms for elliptic equations were studied.
Searching dependency between algebraic equations: An algorithm applied to automated reasoning
International Nuclear Information System (INIS)
Yang Lu; Zhang Jingzhong
1990-01-01
An efficient computer algorithm is given to decide how many branches of the solution to a system of algebraic also solve another equation. As one of the applications, this can be used in practice to verify a conjecture with hypotheses and conclusion expressed by algebraic equations, despite the variety of reducible or irreducible. (author). 10 refs
An algorithm for analysis of the structure of finitely presented Lie algebras
Directory of Open Access Journals (Sweden)
Vladimir P. Gerdt
1997-12-01
Full Text Available We consider the following problem: what is the most general Lie algebra satisfying a given set of Lie polynomial equations? The presentation of Lie algebras by a finite set of generators and defining relations is one of the most general mathematical and algorithmic schemes of their analysis. That problem is of great practical importance, covering applications ranging from mathematical physics to combinatorial algebra. Some particular applications are constructionof prolongation algebras in the Wahlquist-Estabrook method for integrability analysis of nonlinear partial differential equations and investigation of Lie algebras arising in different physical models. The finite presentations also indicate a way to q-quantize Lie algebras. To solve this problem, one should perform a large volume of algebraic transformations which is sharply increased with growth of the number of generators and relations. For this reason, in practice one needs to use a computer algebra tool. We describe here an algorithm for constructing the basis of a finitely presented Lie algebra and its commutator table, and its implementation in the C language. Some computer results illustrating our algorithmand its actual implementation are also presented.
A NetCDF version of the two-dimensional energy balance model based on the full multigrid algorithm
Directory of Open Access Journals (Sweden)
Kelin Zhuang
2017-01-01
Full Text Available A NetCDF version of the two-dimensional energy balance model based on the full multigrid method in Fortran is introduced for both pedagogical and research purposes. Based on the land–sea–ice distribution, orbital elements, greenhouse gases concentration, and albedo, the code calculates the global seasonal surface temperature. A step-by-step guide with examples is provided for practice.
Tabak, John
2004-01-01
Looking closely at algebra, its historical development, and its many useful applications, Algebra examines in detail the question of why this type of math is so important that it arose in different cultures at different times. The book also discusses the relationship between algebra and geometry, shows the progress of thought throughout the centuries, and offers biographical data on the key figures. Concise and comprehensive text accompanied by many illustrations presents the ideas and historical development of algebra, showcasing the relevance and evolution of this branch of mathematics.
Southworth, Benjamin Scott
linear systems arises often in the modeling of biological and physical phenomenon, data analysis through graphs and networks, and other scientific applications. This work focuses primarily on linear systems resulting from the discretization of partial differential equations (PDEs). Because solving linear systems is the bottleneck of many large simulation codes, there is a rich field of research in developing "fast" solvers, with the ultimate goal being a method that solves an n x n linear system in O(n) operations. One of the most effective classes of solvers is algebraic multigrid (AMG), which is a multilevel iterative method based on projecting the problem into progressively smaller spaces, and scales like O(n) or O(nlog n) for certain classes of problems. The field of AMG is well-developed for symmetric positive definite matrices, and is typically most effective on linear systems resulting from the discretization of scalar elliptic PDEs, such as the heat equation. Systems of PDEs can add additional difficulties, but the underlying linear algebraic theory is consistent and, in many cases, an elliptic system of PDEs can be handled well by AMG with appropriate modifications of the solver. Solving general, nonsymmetric linear systems remains the wild west of AMG (and other fast solvers), lacking significant results in convergence theory as well as robust methods. Here, we develop new theoretical motivation and practical variations of AMG to solve nonsymmetric linear systems, often resulting from the discretization of hyperbolic PDEs. In particular, multilevel convergence of AMG for nonsymmetric systems is proven for the first time. A new nonsymmetric AMG solver is also developed based on an approximate ideal restriction, referred to as AIR, which is able to solve advection-dominated, hyperbolic-type problems that are outside the scope of existing AMG solvers and other fast iterative methods. AIR demonstrates scalable convergence on unstructured meshes, in multiple
Semi-coarsening multigrid methods for parallel computing
Energy Technology Data Exchange (ETDEWEB)
Jones, J.E.
1996-12-31
Standard multigrid methods are not well suited for problems with anisotropic coefficients which can occur, for example, on grids that are stretched to resolve a boundary layer. There are several different modifications of the standard multigrid algorithm that yield efficient methods for anisotropic problems. In the paper, we investigate the parallel performance of these multigrid algorithms. Multigrid algorithms which work well for anisotropic problems are based on line relaxation and/or semi-coarsening. In semi-coarsening multigrid algorithms a grid is coarsened in only one of the coordinate directions unlike standard or full-coarsening multigrid algorithms where a grid is coarsened in each of the coordinate directions. When both semi-coarsening and line relaxation are used, the resulting multigrid algorithm is robust and automatic in that it requires no knowledge of the nature of the anisotropy. This is the basic multigrid algorithm whose parallel performance we investigate in the paper. The algorithm is currently being implemented on an IBM SP2 and its performance is being analyzed. In addition to looking at the parallel performance of the basic semi-coarsening algorithm, we present algorithmic modifications with potentially better parallel efficiency. One modification reduces the amount of computational work done in relaxation at the expense of using multiple coarse grids. This modification is also being implemented with the aim of comparing its performance to that of the basic semi-coarsening algorithm.
Extending the applicability of multigrid methods
International Nuclear Information System (INIS)
Brannick, J; Brezina, M; Falgout, R; Manteuffel, T; McCormick, S; Ruge, J; Sheehan, B; Xu, J; Zikatanov, L
2006-01-01
Multigrid methods are ideal for solving the increasingly large-scale problems that arise in numerical simulations of physical phenomena because of their potential for computational costs and memory requirements that scale linearly with the degrees of freedom. Unfortunately, they have been historically limited by their applicability to elliptic-type problems and the need for special handling in their implementation. In this paper, we present an overview of several recent theoretical and algorithmic advances made by the TOPS multigrid partners and their collaborators in extending applicability of multigrid methods. specific examples that are presented include quantum chromodynamics, radiation transport, and electromagnetics
Flanders, Harley
1975-01-01
Algebra presents the essentials of algebra with some applications. The emphasis is on practical skills, problem solving, and computational techniques. Topics covered range from equations and inequalities to functions and graphs, polynomial and rational functions, and exponentials and logarithms. Trigonometric functions and complex numbers are also considered, together with exponentials and logarithms.Comprised of eight chapters, this book begins with a discussion on the fundamentals of algebra, each topic explained, illustrated, and accompanied by an ample set of exercises. The proper use of a
Performance analysis of a decoding algorithm for algebraic-geometry codes
DEFF Research Database (Denmark)
Høholdt, Tom; Jensen, Helge Elbrønd; Nielsen, Rasmus Refslund
1999-01-01
The fast decoding algorithm for one point algebraic-geometry codes of Sakata, Elbrond Jensen, and Hoholdt corrects all error patterns of weight less than half the Feng-Rao minimum distance. In this correspondence we analyze the performance of the algorithm for heavier error patterns. It turns out...
A polynomial time algorithm for checking regularity of totally normed process algebra
Yang, F.; Huang, H.
2015-01-01
A polynomial algorithm for the regularity problem of weak and branching bisimilarity on totally normed process algebra (PA) processes is given. Its time complexity is O(n 3 +mn) O(n3+mn), where n is the number of transition rules and m is the maximal length of the rules. The algorithm works for
An Improved Algorithm for Generating Database Transactions from Relational Algebra Specifications
Directory of Open Access Journals (Sweden)
Daniel J. Dougherty
2010-03-01
Full Text Available Alloy is a lightweight modeling formalism based on relational algebra. In prior work with Fisler, Giannakopoulos, Krishnamurthi, and Yoo, we have presented a tool, Alchemy, that compiles Alloy specifications into implementations that execute against persistent databases. The foundation of Alchemy is an algorithm for rewriting relational algebra formulas into code for database transactions. In this paper we report on recent progress in improving the robustness and efficiency of this transformation.
Ghosh, A
1988-08-01
Lanczos and conjugate gradient algorithms are important in computational linear algebra. In this paper, a parallel pipelined realization of these algorithms on a ring of optical linear algebra processors is described. The flow of data is designed to minimize the idle times of the optical multiprocessor and the redundancy of computations. The effects of optical round-off errors on the solutions obtained by the optical Lanczos and conjugate gradient algorithms are analyzed, and it is shown that optical preconditioning can improve the accuracy of these algorithms substantially. Algorithms for optical preconditioning and results of numerical experiments on solving linear systems of equations arising from partial differential equations are discussed. Since the Lanczos algorithm is used mostly with sparse matrices, a folded storage scheme to represent sparse matrices on spatial light modulators is also described.
Application of Symplectic Algebraic Dynamics Algorithm to Circular Restricted Three-Body Problem
International Nuclear Information System (INIS)
Wei-Tao, Lu; Hua, Zhang; Shun-Jin, Wang
2008-01-01
Symplectic algebraic dynamics algorithm (SADA) for ordinary differential equations is applied to solve numerically the circular restricted three-body problem (CR3BP) in dynamical astronomy for both stable motion and chaotic motion. The result is compared with those of Runge–Kutta algorithm and symplectic algorithm under the fourth order, which shows that SADA has higher accuracy than the others in the long-term calculations of the CR3BP. (general)
Lu, Wei-Tao; Zhang, Hua; Wang, Shun-Jin
2008-07-01
Symplectic algebraic dynamics algorithm (SADA) for ordinary differential equations is applied to solve numerically the circular restricted three-body problem (CR3BP) in dynamical astronomy for both stable motion and chaotic motion. The result is compared with those of Runge-Kutta algorithm and symplectic algorithm under the fourth order, which shows that SADA has higher accuracy than the others in the long-term calculations of the CR3BP.
Sepanski, Mark R
2010-01-01
Mark Sepanski's Algebra is a readable introduction to the delightful world of modern algebra. Beginning with concrete examples from the study of integers and modular arithmetic, the text steadily familiarizes the reader with greater levels of abstraction as it moves through the study of groups, rings, and fields. The book is equipped with over 750 exercises suitable for many levels of student ability. There are standard problems, as well as challenging exercises, that introduce students to topics not normally covered in a first course. Difficult problems are broken into manageable subproblems
Highly indefinite multigrid for eigenvalue problems
Energy Technology Data Exchange (ETDEWEB)
Borges, L.; Oliveira, S.
1996-12-31
Eigenvalue problems are extremely important in understanding dynamic processes such as vibrations and control systems. Large scale eigenvalue problems can be very difficult to solve, especially if a large number of eigenvalues and the corresponding eigenvectors need to be computed. For solving this problem a multigrid preconditioned algorithm is presented in {open_quotes}The Davidson Algorithm, preconditioning and misconvergence{close_quotes}. Another approach for solving eigenvalue problems is by developing efficient solutions for highly indefinite problems. In this paper we concentrate on the use of new highly indefinite multigrid algorithms for the eigenvalue problem.
ALGEBRA: ALgorithm for the heterogeneous dosimetry based on GEANT4 for BRAchytherapy.
Afsharpour, H; Landry, G; D'Amours, M; Enger, S; Reniers, B; Poon, E; Carrier, J-F; Verhaegen, F; Beaulieu, L
2012-06-07
Task group 43 (TG43)-based dosimetry algorithms are efficient for brachytherapy dose calculation in water. However, human tissues have chemical compositions and densities different than water. Moreover, the mutual shielding effect of seeds on each other (interseed attenuation) is neglected in the TG43-based dosimetry platforms. The scientific community has expressed the need for an accurate dosimetry platform in brachytherapy. The purpose of this paper is to present ALGEBRA, a Monte Carlo platform for dosimetry in brachytherapy which is sufficiently fast and accurate for clinical and research purposes. ALGEBRA is based on the GEANT4 Monte Carlo code and is capable of handling the DICOM RT standard to recreate a virtual model of the treated site. Here, the performance of ALGEBRA is presented for the special case of LDR brachytherapy in permanent prostate and breast seed implants. However, the algorithm is also capable of handling other treatments such as HDR brachytherapy.
The Automation of Stochastization Algorithm with Use of SymPy Computer Algebra Library
Demidova, Anastasya; Gevorkyan, Migran; Kulyabov, Dmitry; Korolkova, Anna; Sevastianov, Leonid
2018-02-01
SymPy computer algebra library is used for automatic generation of ordinary and stochastic systems of differential equations from the schemes of kinetic interaction. Schemes of this type are used not only in chemical kinetics but also in biological, ecological and technical models. This paper describes the automatic generation algorithm with an emphasis on application details.
Ltaief, Hatem; Luszczek, Piotr R.; Dongarra, Jack
2011-01-01
This paper presents the power profile of two high performance dense linear algebra libraries i.e., LAPACK and PLASMA. The former is based on block algorithms that use the fork-join paradigm to achieve parallel performance. The latter uses fine
Multigrid for Staggered Lattice Fermions
Energy Technology Data Exchange (ETDEWEB)
Brower, Richard C. [Boston U.; Clark, M. A. [Unlisted, US; Strelchenko, Alexei [Fermilab; Weinberg, Evan [Boston U.
2018-01-23
Critical slowing down in Krylov methods for the Dirac operator presents a major obstacle to further advances in lattice field theory as it approaches the continuum solution. Here we formulate a multi-grid algorithm for the Kogut-Susskind (or staggered) fermion discretization which has proven difficult relative to Wilson multigrid due to its first-order anti-Hermitian structure. The solution is to introduce a novel spectral transformation by the K\\"ahler-Dirac spin structure prior to the Galerkin projection. We present numerical results for the two-dimensional, two-flavor Schwinger model, however, the general formalism is agnostic to dimension and is directly applicable to four-dimensional lattice QCD.
Unweighted least squares phase unwrapping by means of multigrid techniques
Pritt, Mark D.
1995-11-01
We present a multigrid algorithm for unweighted least squares phase unwrapping. This algorithm applies Gauss-Seidel relaxation schemes to solve the Poisson equation on smaller, coarser grids and transfers the intermediate results to the finer grids. This approach forms the basis of our multigrid algorithm for weighted least squares phase unwrapping, which is described in a separate paper. The key idea of our multigrid approach is to maintain the partial derivatives of the phase data in separate arrays and to correct these derivatives at the boundaries of the coarser grids. This maintains the boundary conditions necessary for rapid convergence to the correct solution. Although the multigrid algorithm is an iterative algorithm, we demonstrate that it is nearly as fast as the direct Fourier-based method. We also describe how to parallelize the algorithm for execution on a distributed-memory parallel processor computer or a network-cluster of workstations.
Algebraic Factoring algorithm to recognise read-once functions.
Naidu, S.R.
2003-01-01
A fast polynomial-time algorithm was recently proposed to determine whether a logic function expressed as a unate DNF (disjunctive normal form) can be expressed as a read-once formula where each variable appears no more than once. The paper uses a combinatorial characterisation of read-once formulas
Additional operations in algebra of structural numbers for control algorithm development
Directory of Open Access Journals (Sweden)
Morhun A.V.
2016-12-01
Full Text Available The structural numbers and the algebra of the structural numbers due to the simplicity of representation, flexibility and current algebraic operations are the powerful tool for a wide range of applications. In autonomous power supply systems and systems with distributed generation (Micro Grid mathematical apparatus of structural numbers can be effectively used for the calculation of the parameters of the operating modes of consumption of electric energy. The purpose of the article is the representation of the additional algebra of structural numbers. The standard algebra was proposed to be extended by the additional operations and modification current in order to expand the scope of their use, namely to construct a flexible, adaptive algorithms of control systems. It is achieved due to the possibility to consider each individual component of the system with its parameters and provide easy management of entire system and each individual component. Thus, structural numbers and extended algebra are the perspective line of research and further studying is required.
Is the Multigrid Method Fault Tolerant? The Two-Grid Case
Energy Technology Data Exchange (ETDEWEB)
Ainsworth, Mark [Brown Univ., Providence, RI (United States). Division of Applied Mathematics; Oak Ridge National Lab. (ORNL), Oak Ridge, TN (United States). Computer Science and Mathematics Division; Glusa, Christian [Brown Univ., Providence, RI (United States). Division of Applied Mathematics
2016-06-30
The predicted reduced resiliency of next-generation high performance computers means that it will become necessary to take into account the effects of randomly occurring faults on numerical methods. Further, in the event of a hard fault occurring, a decision has to be made as to what remedial action should be taken in order to resume the execution of the algorithm. The action that is chosen can have a dramatic effect on the performance and characteristics of the scheme. Ideally, the resulting algorithm should be subjected to the same kind of mathematical analysis that was applied to the original, deterministic variant. The purpose of this work is to provide an analysis of the behaviour of the multigrid algorithm in the presence of faults. Multigrid is arguably the method of choice for the solution of large-scale linear algebra problems arising from discretization of partial differential equations and it is of considerable importance to anticipate its behaviour on an exascale machine. The analysis of resilience of algorithms is in its infancy and the current work is perhaps the first to provide a mathematical model for faults and analyse the behaviour of a state-of-the-art algorithm under the model. It is shown that the Two Grid Method fails to be resilient to faults. Attention is then turned to identifying the minimal necessary remedial action required to restore the rate of convergence to that enjoyed by the ideal fault-free method.
International Nuclear Information System (INIS)
Chang, P.; Lee, S.Y.; Yan, Y.T.
2006-01-01
A differential algebraic integration algorithm is developed for symplectic mapping through a three-dimensional (3-D) magnetic field. The self-consistent reference orbit in phase space is obtained by making a canonical transformation to eliminate the linear part of the Hamiltonian. Transfer maps from the entrance to the exit of any 3-D magnetic field are then obtained through slice-by-slice symplectic integration. The particle phase-space coordinates are advanced by using the integrable polynomial procedure. This algorithm is a powerful tool to attain nonlinear maps for insertion devices in synchrotron light source or complicated magnetic field in the interaction region in high energy colliders
International Nuclear Information System (INIS)
Chang, P
2004-01-01
A differential algebraic integration algorithm is developed for symplectic mapping through a three-dimensional (3-D) magnetic field. The self-consistent reference orbit in phase space is obtained by making a canonical transformation to eliminate the linear part of the Hamiltonian. Transfer maps from the entrance to the exit of any 3-D magnetic field are then obtained through slice-by-slice symplectic integration. The particle phase-space coordinates are advanced by using the integrable polynomial procedure. This algorithm is a powerful tool to attain nonlinear maps for insertion devices in synchrotron light source or complicated magnetic field in the interaction region in high energy colliders
Multicloud: Multigrid convergence with a meshless operator
International Nuclear Information System (INIS)
Katz, Aaron; Jameson, Antony
2009-01-01
The primary objective of this work is to develop and test a new convergence acceleration technique we call multicloud. Multicloud is well-founded in the mathematical basis of multigrid, but relies on a meshless operator on coarse levels. The meshless operator enables extremely simple and automatic coarsening procedures for arbitrary meshes using arbitrary fine level discretization schemes. The performance of multicloud is compared with established multigrid techniques for structured and unstructured meshes for the Euler equations on two-dimensional test cases. Results indicate comparable convergence rates per unit work for multicloud and multigrid. However, because of its mesh and scheme transparency, multicloud may be applied to a wide array of problems with no modification of fine level schemes as is often required with agglomeration techniques. The implication is that multicloud can be implemented in a completely modular fashion, allowing researchers to develop fine level algorithms independent of the convergence accelerator for complex three-dimensional problems.
Thirty-three miniatures mathematical and algorithmic applications of linear algebra
Matousek, Jiří
2010-01-01
This volume contains a collection of clever mathematical applications of linear algebra, mainly in combinatorics, geometry, and algorithms. Each chapter covers a single main result with motivation and full proof in at most ten pages and can be read independently of all other chapters (with minor exceptions), assuming only a modest background in linear algebra. The topics include a number of well-known mathematical gems, such as Hamming codes, the matrix-tree theorem, the Lov�sz bound on the Shannon capacity, and a counterexample to Borsuk's conjecture, as well as other, perhaps less popular but similarly beautiful results, e.g., fast associativity testing, a lemma of Steinitz on ordering vectors, a monotonicity result for integer partitions, or a bound for set pairs via exterior products. The simpler results in the first part of the book provide ample material to liven up an undergraduate course of linear algebra. The more advanced parts can be used for a graduate course of linear-algebraic methods or for s...
Trottenberg, U; Third European Conference on Multigrid Methods
1991-01-01
These proceedings contain a selection of papers presented at the Third European Conference on Multigrid Methods which was held in Bonn on October 1-4, 1990. Following conferences in 1981 and 1985, a platform for the presentation of new Multigrid results was provided for a third time. Multigrid methods no longer have problems being accepted by numerical analysts and users of numerical methods; on the contrary, they have been further developed in such a successful way that they have penetrated a variety of new fields of application. The high number of 154 participants from 18 countries and 76 presented papers show the need to continue the series of the European Multigrid Conferences. The papers of this volume give a survey on the current Multigrid situation; in particular, they correspond to those fields where new developments can be observed. For example, se veral papers study the appropriate treatment of time dependent problems. Improvements can also be noticed in the Multigrid approach for semiconductor eq...
Global identifiability of linear compartmental models--a computer algebra algorithm.
Audoly, S; D'Angiò, L; Saccomani, M P; Cobelli, C
1998-01-01
A priori global identifiability deals with the uniqueness of the solution for the unknown parameters of a model and is, thus, a prerequisite for parameter estimation of biological dynamic models. Global identifiability is however difficult to test, since it requires solving a system of algebraic nonlinear equations which increases both in nonlinearity degree and number of terms and unknowns with increasing model order. In this paper, a computer algebra tool, GLOBI (GLOBal Identifiability) is presented, which combines the topological transfer function method with the Buchberger algorithm, to test global identifiability of linear compartmental models. GLOBI allows for the automatic testing of a priori global identifiability of general structure compartmental models from general multi input-multi output experiments. Examples of usage of GLOBI to analyze a priori global identifiability of some complex biological compartmental models are provided.
Design and Implementation of Numerical Linear Algebra Algorithms on Fixed Point DSPs
Directory of Open Access Journals (Sweden)
Gene Frantz
2007-01-01
Full Text Available Numerical linear algebra algorithms use the inherent elegance of matrix formulations and are usually implemented using C/C++ floating point representation. The system implementation is faced with practical constraints because these algorithms usually need to run in real time on fixed point digital signal processors (DSPs to reduce total hardware costs. Converting the simulation model to fixed point arithmetic and then porting it to a target DSP device is a difficult and time-consuming process. In this paper, we analyze the conversion process. We transformed selected linear algebra algorithms from floating point to fixed point arithmetic, and compared real-time requirements and performance between the fixed point DSP and floating point DSP algorithm implementations. We also introduce an advanced code optimization and an implementation by DSP-specific, fixed point C code generation. By using the techniques described in the paper, speed can be increased by a factor of up to 10 compared to floating point emulation on fixed point hardware.
The Mixed Finite Element Multigrid Method for Stokes Equations
Muzhinji, K.; Shateyi, S.; Motsa, S. S.
2015-01-01
The stable finite element discretization of the Stokes problem produces a symmetric indefinite system of linear algebraic equations. A variety of iterative solvers have been proposed for such systems in an attempt to construct efficient, fast, and robust solution techniques. This paper investigates one of such iterative solvers, the geometric multigrid solver, to find the approximate solution of the indefinite systems. The main ingredient of the multigrid method is the choice of an appropriate smoothing strategy. This study considers the application of different smoothers and compares their effects in the overall performance of the multigrid solver. We study the multigrid method with the following smoothers: distributed Gauss Seidel, inexact Uzawa, preconditioned MINRES, and Braess-Sarazin type smoothers. A comparative study of the smoothers shows that the Braess-Sarazin smoothers enhance good performance of the multigrid method. We study the problem in a two-dimensional domain using stable Hood-Taylor Q 2-Q 1 pair of finite rectangular elements. We also give the main theoretical convergence results. We present the numerical results to demonstrate the efficiency and robustness of the multigrid method and confirm the theoretical results. PMID:25945361
Multigrid methods for the computation of propagators in gauge fields
International Nuclear Information System (INIS)
Kalkreuter, T.
1992-11-01
In the present work generalizations of multigrid methods for propagators in gauge fields are investigated. We discuss proper averaging operations for bosons and for staggered fermions. An efficient algorithm for computing C numerically is presented. The averaging kernels C can be used not only in deterministic multigrid computations, but also in multigrid Monte Carlo simulations, and for the definition of block spins and blocked gauge fields in Monte Carlo renormalization group studies of gauge theories. Actual numerical computations of kernels and propagators are performed in compact four-dimensional SU(2) gauge fields. (orig./HSI)
Progress with multigrid schemes for hypersonic flow problems
International Nuclear Information System (INIS)
Radespiel, R.; Swanson, R.C.
1995-01-01
Several multigrid schemes are considered for the numerical computation of viscous hypersonic flows. For each scheme, the basic solution algorithm employs upwind spatial discretization with explicit multistage time stepping. Two-level versions of the various multigrid algorithms are applied to the two-dimensional advection equation, and Fourier analysis is used to determine their damping properties. The capabilities of the multigrid methods are assessed by solving three different hypersonic flow problems. Some new multigrid schemes based on semicoarsening strategies are shown to be quite effective in relieving the stiffness caused by the high-aspect-ratio cells required to resolve high Reynolds number flows. These schemes exhibit good convergence rates for Reynolds numbers up to 200 X 10 6 and Mach numbers up to 25. 32 refs., 31 figs., 1 tab
Algorithms of estimation for nonlinear systems a differential and algebraic viewpoint
Martínez-Guerra, Rafael
2017-01-01
This book acquaints readers with recent developments in dynamical systems theory and its applications, with a strong focus on the control and estimation of nonlinear systems. Several algorithms are proposed and worked out for a set of model systems, in particular so-called input-affine or bilinear systems, which can serve to approximate a wide class of nonlinear control systems. These can either take the form of state space models or be represented by an input-output equation. The approach taken here further highlights the role of modern mathematical and conceptual tools, including differential algebraic theory, observer design for nonlinear systems and generalized canonical forms.
Zimmermann, Ralf
2016-01-01
We derive a numerical algorithm for evaluating the Riemannian logarithm on the Stiefel manifold with respect to the canonical metric. In contrast to the optimization-based approach known from the literature, we work from a purely matrix-algebraic perspective. Moreover, we prove that the algorithm converges locally and exhibits a linear rate of convergence.
DEFF Research Database (Denmark)
Zimmermann, Ralf
2017-01-01
We derive a numerical algorithm for evaluating the Riemannian logarithm on the Stiefel manifold with respect to the canonical metric. In contrast to the optimization-based approach known from the literature, we work from a purely matrix-algebraic perspective. Moreover, we prove that the algorithm...... converges locally and exhibits a linear rate of convergence....
Final report on the Copper Mountain conference on multigrid methods
Energy Technology Data Exchange (ETDEWEB)
NONE
1997-10-01
The Copper Mountain Conference on Multigrid Methods was held on April 6-11, 1997. It took the same format used in the previous Copper Mountain Conferences on Multigrid Method conferences. Over 87 mathematicians from all over the world attended the meeting. 56 half-hour talks on current research topics were presented. Talks with similar content were organized into sessions. Session topics included: fluids; domain decomposition; iterative methods; basics; adaptive methods; non-linear filtering; CFD; applications; transport; algebraic solvers; supercomputing; and student paper winners.
Design Considerations for a Flexible Multigrid Preconditioning Library
Directory of Open Access Journals (Sweden)
Jérémie Gaidamour
2012-01-01
Full Text Available MueLu is a library within the Trilinos software project [An overview of Trilinos, Technical Report SAND2003-2927, Sandia National Laboratories, 2003] and provides a framework for parallel multigrid preconditioning methods for large sparse linear systems. While providing efficient implementations of modern multigrid methods based on smoothed aggregation and energy minimization concepts, MueLu is designed to be customized and extended. This article gives an overview of design considerations for the MueLu package: user interfaces, internal design, data management, usage of modern software constructs, leveraging Trilinos capabilities, linear algebra operations and advanced application.
Ground-state projection multigrid for propagators in 4-dimensional SU(2) gauge fields
International Nuclear Information System (INIS)
Kalkreuter, T.
1991-09-01
The ground-state projection multigrid method is studied for computations of slowly decaying bosonic propagators in 4-dimensional SU(2) lattice gauge theory. The defining eigenvalue equation for the restriction operator is solved exactly. Although the critical exponent z is not reduced in nontrivial gauge fields, multigrid still yields considerable speedup compared with conventional relaxation. Multigrid is also able to outperform the conjugate gradient algorithm. (orig.)
Ltaief, Hatem
2011-08-31
This paper presents the power profile of two high performance dense linear algebra libraries i.e., LAPACK and PLASMA. The former is based on block algorithms that use the fork-join paradigm to achieve parallel performance. The latter uses fine-grained task parallelism that recasts the computation to operate on submatrices called tiles. In this way tile algorithms are formed. We show results from the power profiling of the most common routines, which permits us to clearly identify the different phases of the computations. This allows us to isolate the bottlenecks in terms of energy efficiency. Our results show that PLASMA surpasses LAPACK not only in terms of performance but also in terms of energy efficiency. © 2011 Springer-Verlag.
New matrix bounds and iterative algorithms for the discrete coupled algebraic Riccati equation
Liu, Jianzhou; Wang, Li; Zhang, Juan
2017-11-01
The discrete coupled algebraic Riccati equation (DCARE) has wide applications in control theory and linear system. In general, for the DCARE, one discusses every term of the coupled term, respectively. In this paper, we consider the coupled term as a whole, which is different from the recent results. When applying eigenvalue inequalities to discuss the coupled term, our method has less error. In terms of the properties of special matrices and eigenvalue inequalities, we propose several upper and lower matrix bounds for the solution of DCARE. Further, we discuss the iterative algorithms for the solution of the DCARE. In the fixed point iterative algorithms, the scope of Lipschitz factor is wider than the recent results. Finally, we offer corresponding numerical examples to illustrate the effectiveness of the derived results.
Dongarra, Jack; Ltaief, Hatem; Luszczek, Piotr R.; Weaver, Vincent M.
2012-01-01
We propose to study the impact on the energy footprint of two advanced algorithmic strategies in the context of high performance dense linear algebra libraries: (1) mixed precision algorithms with iterative refinement allow to run at the peak performance of single precision floating-point arithmetic while achieving double precision accuracy and (2) tree reduction technique exposes more parallelism when factorizing tall and skinny matrices for solving over determined systems of linear equations or calculating the singular value decomposition. Integrated within the PLASMA library using tile algorithms, which will eventually supersede the block algorithms from LAPACK, both strategies further excel in performance in the presence of a dynamic task scheduler while targeting multicore architecture. Energy consumption measurements are reported along with parallel performance numbers on a dual-socket quad-core Intel Xeon as well as a quad-socket quad-core Intel Sandy Bridge chip, both providing component-based energy monitoring at all levels of the system, through the Power Pack framework and the Running Average Power Limit model, respectively. © 2012 IEEE.
Dongarra, Jack
2012-11-01
We propose to study the impact on the energy footprint of two advanced algorithmic strategies in the context of high performance dense linear algebra libraries: (1) mixed precision algorithms with iterative refinement allow to run at the peak performance of single precision floating-point arithmetic while achieving double precision accuracy and (2) tree reduction technique exposes more parallelism when factorizing tall and skinny matrices for solving over determined systems of linear equations or calculating the singular value decomposition. Integrated within the PLASMA library using tile algorithms, which will eventually supersede the block algorithms from LAPACK, both strategies further excel in performance in the presence of a dynamic task scheduler while targeting multicore architecture. Energy consumption measurements are reported along with parallel performance numbers on a dual-socket quad-core Intel Xeon as well as a quad-socket quad-core Intel Sandy Bridge chip, both providing component-based energy monitoring at all levels of the system, through the Power Pack framework and the Running Average Power Limit model, respectively. © 2012 IEEE.
Multigrid treatment of implicit continuum diffusion
Francisquez, Manaure; Zhu, Ben; Rogers, Barrett
2017-10-01
Implicit treatment of diffusive terms of various differential orders common in continuum mechanics modeling, such as computational fluid dynamics, is investigated with spectral and multigrid algorithms in non-periodic 2D domains. In doubly periodic time dependent problems these terms can be efficiently and implicitly handled by spectral methods, but in non-periodic systems solved with distributed memory parallel computing and 2D domain decomposition, this efficiency is lost for large numbers of processors. We built and present here a multigrid algorithm for these types of problems which outperforms a spectral solution that employs the highly optimized FFTW library. This multigrid algorithm is not only suitable for high performance computing but may also be able to efficiently treat implicit diffusion of arbitrary order by introducing auxiliary equations of lower order. We test these solvers for fourth and sixth order diffusion with idealized harmonic test functions as well as a turbulent 2D magnetohydrodynamic simulation. It is also shown that an anisotropic operator without cross-terms can improve model accuracy and speed, and we examine the impact that the various diffusion operators have on the energy, the enstrophy, and the qualitative aspect of a simulation. This work was supported by DOE-SC-0010508. This research used resources of the National Energy Research Scientific Computing Center (NERSC).
Energy Technology Data Exchange (ETDEWEB)
Bennett, Janine Camille [Sandia National Lab. (SNL-CA), Livermore, CA (United States). Visualization and Scientific Computing Dept.; Day, David Minot [Sandia National Lab. (SNL-NM), Albuquerque, NM (United States). Applied Mathematics and Applications Dept.; Mitchell, Scott A. [Sandia National Lab. (SNL-NM), Albuquerque, NM (United States). Computer Science and Informatics Dept.
2009-11-20
This report summarizes the Combinatorial Algebraic Topology: software, applications & algorithms workshop (CAT Workshop). The workshop was sponsored by the Computer Science Research Institute of Sandia National Laboratories. It was organized by CSRI staff members Scott Mitchell and Shawn Martin. It was held in Santa Fe, New Mexico, August 29-30. The CAT Workshop website has links to some of the talk slides and other information, http://www.cs.sandia.gov/CSRI/Workshops/2009/CAT/index.html. The purpose of the report is to summarize the discussions and recap the sessions. There is a special emphasis on technical areas that are ripe for further exploration, and the plans for follow-up amongst the workshop participants. The intended audiences are the workshop participants, other researchers in the area, and the workshop sponsors.
Energy Technology Data Exchange (ETDEWEB)
Lee, E.T.
1983-01-01
Algorithms for the construction of the Chomsky and Greibach normal forms for a fuzzy context-free grammar using the algebraic approach are presented and illustrated by examples. The results obtained in this paper may have useful applications in fuzzy languages, pattern recognition, information storage and retrieval, artificial intelligence, database and pictorial information systems. 16 references.
International Nuclear Information System (INIS)
Littlefield, R.J.; Maschhoff, K.J.
1991-04-01
Many linear algebra algorithms utilize an array of processors across which matrices are distributed. Given a particular matrix size and a maximum number of processors, what configuration of processors, i.e., what size and shape array, will execute the fastest? The answer to this question depends on tradeoffs between load balancing, communication startup and transfer costs, and computational overhead. In this paper we analyze in detail one algorithm: the blocked factored Jacobi method for solving dense eigensystems. A performance model is developed to predict execution time as a function of the processor array and matrix sizes, plus the basic computation and communication speeds of the underlying computer system. In experiments on a large hypercube (up to 512 processors), this model has been found to be highly accurate (mean error ∼ 2%) over a wide range of matrix sizes (10 x 10 through 200 x 200) and processor counts (1 to 512). The model reveals, and direct experiment confirms, that the tradeoffs mentioned above can be surprisingly complex and counterintuitive. We propose decision procedures based directly on the performance model to choose configurations for fastest execution. The model-based decision procedures are compared to a heuristic strategy and shown to be significantly better. 7 refs., 8 figs., 1 tab
Multigrid and multilevel domain decomposition for unstructured grids
Energy Technology Data Exchange (ETDEWEB)
Chan, T.; Smith, B.
1994-12-31
Multigrid has proven itself to be a very versatile method for the iterative solution of linear and nonlinear systems of equations arising from the discretization of PDES. In some applications, however, no natural multilevel structure of grids is available, and these must be generated as part of the solution procedure. In this presentation the authors will consider the problem of generating a multigrid algorithm when only a fine, unstructured grid is given. Their techniques generate a sequence of coarser grids by first forming an approximate maximal independent set of the vertices and then applying a Cavendish type algorithm to form the coarser triangulation. Numerical tests indicate that convergence using this approach can be as fast as standard multigrid on a structured mesh, at least in two dimensions.
International Nuclear Information System (INIS)
Solchenbach, K.; Thole, C.A.; Trottenberg, U.
1987-01-01
For a wide class of problems in scientific computing, in particular for partial differential equations, the multigrid principle has proved to yield highly efficient numerical methods. However, the principle has to be applied carefully: if the multigrid components are not chosen adequately with respect to the given problem, the efficiency may be much smaller than possible. This has been demonstrated for many practical problems. Unfortunately, the general theories on multigrid convergence do not give much help in constructing really efficient multigrid algorithms. Although some progress has been made in bridging the gap between theory and practice during the last few years, there are still several theoretical approaches which are misleading rather than helpful with respect to the objective of real efficiency. The research in finding highly efficient algorithms for non-model applications therefore is still a sophisticated mixture of theoretical considerations, a transfer of experiences from model to real life problems and systematical experimental work. The emphasis of the practical research activity today lies - among others - in the following fields: - finding efficient multigrid components for really complex problems, - combining the multigrid approach with advanced discretizative techniques: - constructing highly parallel multigrid algorithms. In this paper, we want to deal mainly with the last topic
Parallel multigrid smoothing: polynomial versus Gauss-Seidel
International Nuclear Information System (INIS)
Adams, Mark; Brezina, Marian; Hu, Jonathan; Tuminaro, Ray
2003-01-01
Gauss-Seidel is often the smoother of choice within multigrid applications. In the context of unstructured meshes, however, maintaining good parallel efficiency is difficult with multiplicative iterative methods such as Gauss-Seidel. This leads us to consider alternative smoothers. We discuss the computational advantages of polynomial smoothers within parallel multigrid algorithms for positive definite symmetric systems. Two particular polynomials are considered: Chebyshev and a multilevel specific polynomial. The advantages of polynomial smoothing over traditional smoothers such as Gauss-Seidel are illustrated on several applications: Poisson's equation, thin-body elasticity, and eddy current approximations to Maxwell's equations. While parallelizing the Gauss-Seidel method typically involves a compromise between a scalable convergence rate and maintaining high flop rates, polynomial smoothers achieve parallel scalable multigrid convergence rates without sacrificing flop rates. We show that, although parallel computers are the main motivation, polynomial smoothers are often surprisingly competitive with Gauss-Seidel smoothers on serial machines
Parallel multigrid smoothing: polynomial versus Gauss-Seidel
Adams, Mark; Brezina, Marian; Hu, Jonathan; Tuminaro, Ray
2003-07-01
Gauss-Seidel is often the smoother of choice within multigrid applications. In the context of unstructured meshes, however, maintaining good parallel efficiency is difficult with multiplicative iterative methods such as Gauss-Seidel. This leads us to consider alternative smoothers. We discuss the computational advantages of polynomial smoothers within parallel multigrid algorithms for positive definite symmetric systems. Two particular polynomials are considered: Chebyshev and a multilevel specific polynomial. The advantages of polynomial smoothing over traditional smoothers such as Gauss-Seidel are illustrated on several applications: Poisson's equation, thin-body elasticity, and eddy current approximations to Maxwell's equations. While parallelizing the Gauss-Seidel method typically involves a compromise between a scalable convergence rate and maintaining high flop rates, polynomial smoothers achieve parallel scalable multigrid convergence rates without sacrificing flop rates. We show that, although parallel computers are the main motivation, polynomial smoothers are often surprisingly competitive with Gauss-Seidel smoothers on serial machines.
Cavaglieri, Daniele; Bewley, Thomas; Mashayek, Ali
2015-11-01
We present a new code, Diablo 2.0, for the simulation of the incompressible NSE in channel and duct flows with strong grid stretching near walls. The code leverages the fractional step approach with a few twists. New low-storage IMEX (implicit-explicit) Runge-Kutta time-marching schemes are tested which are superior to the traditional and widely-used CN/RKW3 (Crank-Nicolson/Runge-Kutta-Wray) approach; the new schemes tested are L-stable in their implicit component, and offer improved overall order of accuracy and stability with, remarkably, similar computational cost and storage requirements. For duct flow simulations, our new code also introduces a new smoother for the multigrid solver for the pressure Poisson equation. The classic approach, involving alternating-direction zebra relaxation, is replaced by a new scheme, dubbed tweed relaxation, which achieves the same convergence rate with roughly half the computational cost. The code is then tested on the simulation of a shear flow instability in a duct, a classic problem in fluid mechanics which has been the object of extensive numerical modelling for its role as a canonical pathway to energetic turbulence in several fields of science and engineering.
Multigrid Methods for the Computation of Propagators in Gauge Fields
Kalkreuter, Thomas
Multigrid methods were invented for the solution of discretized partial differential equations in order to overcome the slowness of traditional algorithms by updates on various length scales. In the present work generalizations of multigrid methods for propagators in gauge fields are investigated. Gauge fields are incorporated in algorithms in a covariant way. The kernel C of the restriction operator which averages from one grid to the next coarser grid is defined by projection on the ground-state of a local Hamiltonian. The idea behind this definition is that the appropriate notion of smoothness depends on the dynamics. The ground-state projection choice of C can be used in arbitrary dimension and for arbitrary gauge group. We discuss proper averaging operations for bosons and for staggered fermions. The kernels C can also be used in multigrid Monte Carlo simulations, and for the definition of block spins and blocked gauge fields in Monte Carlo renormalization group studies. Actual numerical computations are performed in four-dimensional SU(2) gauge fields. We prove that our proposals for block spins are “good”, using renormalization group arguments. A central result is that the multigrid method works in arbitrarily disordered gauge fields, in principle. It is proved that computations of propagators in gauge fields without critical slowing down are possible when one uses an ideal interpolation kernel. Unfortunately, the idealized algorithm is not practical, but it was important to answer questions of principle. Practical methods are able to outperform the conjugate gradient algorithm in case of bosons. The case of staggered fermions is harder. Multigrid methods give considerable speed-ups compared to conventional relaxation algorithms, but on lattices up to 184 conjugate gradient is superior.
Efficient relaxed-Jacobi smoothers for multigrid on parallel computers
Yang, Xiang; Mittal, Rajat
2017-03-01
In this Technical Note, we present a family of Jacobi-based multigrid smoothers suitable for the solution of discretized elliptic equations. These smoothers are based on the idea of scheduled-relaxation Jacobi proposed recently by Yang & Mittal (2014) [18] and employ two or three successive relaxed Jacobi iterations with relaxation factors derived so as to maximize the smoothing property of these iterations. The performance of these new smoothers measured in terms of convergence acceleration and computational workload, is assessed for multi-domain implementations typical of parallelized solvers, and compared to the lexicographic point Gauss-Seidel smoother. The tests include the geometric multigrid method on structured grids as well as the algebraic grid method on unstructured grids. The tests demonstrate that unlike Gauss-Seidel, the convergence of these Jacobi-based smoothers is unaffected by domain decomposition, and furthermore, they outperform the lexicographic Gauss-Seidel by factors that increase with domain partition count.
Achieving Textbook Multigrid Efficiency for Hydrostatic Ice Sheet Flow
Brown, Jed
2013-03-12
The hydrostatic equations for ice sheet flow offer improved fidelity compared with the shallow ice approximation and shallow stream approximation popular in today\\'s ice sheet models. Nevertheless, they present a serious bottleneck because they require the solution of a three-dimensional (3D) nonlinear system, as opposed to the two-dimensional system present in the shallow stream approximation. This 3D system is posed on high-aspect domains with strong anisotropy and variation in coefficients, making it expensive to solve with current methods. This paper presents a Newton--Krylov multigrid solver for the hydrostatic equations that demonstrates textbook multigrid efficiency (an order of magnitude reduction in residual per iteration and solution of the fine-level system at a small multiple of the cost of a residual evaluation). Scalability on Blue Gene/P is demonstrated, and the method is compared to various algebraic methods that are in use or have been proposed as viable approaches.
Achieving Textbook Multigrid Efficiency for Hydrostatic Ice Sheet Flow
Brown, Jed; Smith, Barry; Ahmadia, Aron
2013-01-01
The hydrostatic equations for ice sheet flow offer improved fidelity compared with the shallow ice approximation and shallow stream approximation popular in today's ice sheet models. Nevertheless, they present a serious bottleneck because they require the solution of a three-dimensional (3D) nonlinear system, as opposed to the two-dimensional system present in the shallow stream approximation. This 3D system is posed on high-aspect domains with strong anisotropy and variation in coefficients, making it expensive to solve with current methods. This paper presents a Newton--Krylov multigrid solver for the hydrostatic equations that demonstrates textbook multigrid efficiency (an order of magnitude reduction in residual per iteration and solution of the fine-level system at a small multiple of the cost of a residual evaluation). Scalability on Blue Gene/P is demonstrated, and the method is compared to various algebraic methods that are in use or have been proposed as viable approaches.
Nonlinear Multigrid solver exploiting AMGe Coarse Spaces with Approximation Properties
DEFF Research Database (Denmark)
Christensen, Max la Cour; Villa, Umberto; Engsig-Karup, Allan Peter
The paper introduces a nonlinear multigrid solver for mixed finite element discretizations based on the Full Approximation Scheme (FAS) and element-based Algebraic Multigrid (AMGe). The main motivation to use FAS for unstructured problems is the guaranteed approximation property of the AMGe coarse...... properties of the coarse spaces. With coarse spaces with approximation properties, our FAS approach on unstructured meshes has the ability to be as powerful/successful as FAS on geometrically refined meshes. For comparison, Newton’s method and Picard iterations with an inner state-of-the-art linear solver...... are compared to FAS on a nonlinear saddle point problem with applications to porous media flow. It is demonstrated that FAS is faster than Newton’s method and Picard iterations for the experiments considered here. Due to the guaranteed approximation properties of our AMGe, the coarse spaces are very accurate...
Edwards, Harold M
1995-01-01
In his new undergraduate textbook, Harold M Edwards proposes a radically new and thoroughly algorithmic approach to linear algebra Originally inspired by the constructive philosophy of mathematics championed in the 19th century by Leopold Kronecker, the approach is well suited to students in the computer-dominated late 20th century Each proof is an algorithm described in English that can be translated into the computer language the class is using and put to work solving problems and generating new examples, making the study of linear algebra a truly interactive experience Designed for a one-semester course, this text adopts an algorithmic approach to linear algebra giving the student many examples to work through and copious exercises to test their skills and extend their knowledge of the subject Students at all levels will find much interactive instruction in this text while teachers will find stimulating examples and methods of approach to the subject
Genetic algorithms in teaching artificial intelligence (automated generation of specific algebras)
Habiballa, Hashim; Jendryscik, Radek
2017-11-01
The problem of teaching essential Artificial Intelligence (AI) methods is an important task for an educator in the branch of soft-computing. The key focus is often given to proper understanding of the principle of AI methods in two essential points - why we use soft-computing methods at all and how we apply these methods to generate reasonable results in sensible time. We present one interesting problem solved in the non-educational research concerning automated generation of specific algebras in the huge search space. We emphasize above mentioned points as an educational case study of an interesting problem in automated generation of specific algebras.
Finite volume multigrid method of the planar contraction flow of a viscoelastic fluid
Moatssime, H. Al; Esselaoui, D.; Hakim, A.; Raghay, S.
2001-08-01
This paper reports on a numerical algorithm for the steady flow of viscoelastic fluid. The conservative and constitutive equations are solved using the finite volume method (FVM) with a hybrid scheme for the velocities and first-order upwind approximation for the viscoelastic stress. A non-uniform staggered grid system is used. The iterative SIMPLE algorithm is employed to relax the coupled momentum and continuity equations. The non-linear algebraic equations over the flow domain are solved iteratively by the symmetrical coupled Gauss-Seidel (SCGS) method. In both, the full approximation storage (FAS) multigrid algorithm is used. An Oldroyd-B fluid model was selected for the calculation. Results are reported for planar 4:1 abrupt contraction at various Weissenberg numbers. The solutions are found to be stable and smooth. The solutions show that at high Weissenberg number the domain must be long enough. The convergence of the method has been verified with grid refinement. All the calculations have been performed on a PC equipped with a Pentium III processor at 550 MHz. Copyright
Copper Mountain conference on multigrid methods. Preliminary proceedings -- List of abstracts
Energy Technology Data Exchange (ETDEWEB)
NONE
1995-12-31
This report contains abstracts of the papers presented at the conference. Papers cover multigrid algorithms and applications of multigrid methods. Applications include the following: solution of elliptical problems; electric power grids; fluid mechanics; atmospheric data assimilation; thermocapillary effects on weld pool shape; boundary-value problems; prediction of hurricane tracks; modeling multi-dimensional combustion and detailed chemistry; black-oil reservoir simulation; image processing; and others.
Directory of Open Access Journals (Sweden)
Fabio Henrique Pereira
2009-01-01
Full Text Available In this work the performance of ¿-cycle wavelet-based algebraic multigrid preconditioner for iterative methods is investigated. The method is applied as a preconditioner for the classical iterative methods Bi-Conjugate Gradient Stabilized (BiCGStab, Generalized Minimum Residual (GMRes and Conjugate Gradient (CG to the solution of non-linear system of algebraic equations from the analysis of a switched reluctance motor with ferromagnetic material the steel S45C and nonlinear magnetization curve, associated with the Newton-Raphson algorithm. Particular attention has been focused in both V- and W-cycle convergence factors, as well as the CPU time. Numerical results show the efficiency of the proposed techniques when compared with classical preconditioner, such as Incomplete Cholesky and Incomplete LU decomposition.
Uniform convergence of multigrid V-cycle iterations for indefinite and nonsymmetric problems
Bramble, James H.; Kwak, Do Y.; Pasciak, Joseph E.
1993-01-01
In this paper, we present an analysis of a multigrid method for nonsymmetric and/or indefinite elliptic problems. In this multigrid method various types of smoothers may be used. One type of smoother which we consider is defined in terms of an associated symmetric problem and includes point and line, Jacobi, and Gauss-Seidel iterations. We also study smoothers based entirely on the original operator. One is based on the normal form, that is, the product of the operator and its transpose. Other smoothers studied include point and line, Jacobi, and Gauss-Seidel. We show that the uniform estimates for symmetric positive definite problems carry over to these algorithms. More precisely, the multigrid iteration for the nonsymmetric and/or indefinite problem is shown to converge at a uniform rate provided that the coarsest grid in the multilevel iteration is sufficiently fine (but not depending on the number of multigrid levels).
On a multigrid method for the coupled Stokes and porous media flow problem
Luo, P.; Rodrigo, C.; Gaspar, F. J.; Oosterlee, C. W.
2017-07-01
The multigrid solution of coupled porous media and Stokes flow problems is considered. The Darcy equation as the saturated porous medium model is coupled to the Stokes equations by means of appropriate interface conditions. We focus on an efficient multigrid solution technique for the coupled problem, which is discretized by finite volumes on staggered grids, giving rise to a saddle point linear system. Special treatment is required regarding the discretization at the interface. An Uzawa smoother is employed in multigrid, which is a decoupled procedure based on symmetric Gauss-Seidel smoothing for velocity components and a simple Richardson iteration for the pressure field. Since a relaxation parameter is part of a Richardson iteration, Local Fourier Analysis (LFA) is applied to determine the optimal parameters. Highly satisfactory multigrid convergence is reported, and, moreover, the algorithm performs well for small values of the hydraulic conductivity and fluid viscosity, that are relevant for applications.
Institute of Scientific and Technical Information of China (English)
无
2010-01-01
We give an equivalent construction of the infinitesimal time translation operator for partial differential evolution equation in the algebraic dynamics algorithm proposed by Shun-Jin Wang and his students. Our construction involves only simple partial differentials and avoids the derivative terms of δ function which appear in the course of computation by means of Wang-Zhang operator. We prove Wang’s equivalent theorem which says that our construction and Wang-Zhang’s are equivalent. We use our construction to deal with several typical equations such as nonlinear advection equation, Burgers equation, nonlinear Schrodinger equation, KdV equation and sine-Gordon equation, and obtain at least second order approximate solutions to them. These equations include the cases of real and complex field variables and the cases of the first and the second order time derivatives.
Conjugate gradient coupled with multigrid for an indefinite problem
Gozani, J.; Nachshon, A.; Turkel, E.
1984-01-01
An iterative algorithm for the Helmholtz equation is presented. This scheme was based on the preconditioned conjugate gradient method for the normal equations. The preconditioning is one cycle of a multigrid method for the discrete Laplacian. The smoothing algorithm is red-black Gauss-Seidel and is constructed so it is a symmetric operator. The total number of iterations needed by the algorithm is independent of h. By varying the number of grids, the number of iterations depends only weakly on k when k(3)h(2) is constant. Comparisons with a SSOR preconditioner are presented.
Directory of Open Access Journals (Sweden)
A. A. Zolotin
2015-07-01
Full Text Available Posteriori inference is one of the three kinds of probabilistic-logic inferences in the probabilistic graphical models theory and the base for processing of knowledge patterns with probabilistic uncertainty using Bayesian networks. The paper deals with a task of local posteriori inference description in algebraic Bayesian networks that represent a class of probabilistic graphical models by means of matrix-vector equations. The latter are essentially based on the use of tensor product of matrices, Kronecker degree and Hadamard product. Matrix equations for calculating posteriori probabilities vectors within posteriori inference in knowledge patterns with quanta propositions are obtained. Similar equations of the same type have already been discussed within the confines of the theory of algebraic Bayesian networks, but they were built only for the case of posteriori inference in the knowledge patterns on the ideals of conjuncts. During synthesis and development of matrix-vector equations on quanta propositions probability vectors, a number of earlier results concerning normalizing factors in posteriori inference and assignment of linear projective operator with a selector vector was adapted. We consider all three types of incoming evidences - deterministic, stochastic and inaccurate - combined with scalar and interval estimation of probability truth of propositional formulas in the knowledge patterns. Linear programming problems are formed. Their solution gives the desired interval values of posterior probabilities in the case of inaccurate evidence or interval estimates in a knowledge pattern. That sort of description of a posteriori inference gives the possibility to extend the set of knowledge pattern types that we can use in the local and global posteriori inference, as well as simplify complex software implementation by use of existing third-party libraries, effectively supporting submission and processing of matrices and vectors when
Multigrid Computation of Stratified Flow over Two-Dimensional Obstacles
Paisley, M. F.
1997-09-01
A robust multigrid method for the incompressible Navier-Stokes equations is presented and applied to the computation of viscous flow over obstacles in a bounded domain under conditions of neutral stability and stable density stratification. Two obstacle shapes have been used, namely a vertical barrier, for which the grid is Cartesian, and a smooth cosine-shaped obstacle, for which a boundary-conforming transformation is incorporated. Results are given for laminar flows at low Reynolds numbers and turbulent flows at a high Reynolds number, when a simple mixing length turbulence model is included. The multigrid algorithm is used to compute steady flows for each obstacle at low and high Reynolds numbers in conditions of weak static stability, defined byK=ND/πU≤ 1, whereU,N, andDare the upstream velocity, bouyancy frequency, and domain height respectively. Results are also presented for the vertical barrier at low and high Reynolds number in conditions of strong static stability,K> 1, when lee wave motions ensure that the flow is unsteady, and the multigrid algorithm is used to compute the flow at each timestep.
Computer algebra and operators
Fateman, Richard; Grossman, Robert
1989-01-01
The symbolic computation of operator expansions is discussed. Some of the capabilities that prove useful when performing computer algebra computations involving operators are considered. These capabilities may be broadly divided into three areas: the algebraic manipulation of expressions from the algebra generated by operators; the algebraic manipulation of the actions of the operators upon other mathematical objects; and the development of appropriate normal forms and simplification algorithms for operators and their actions. Brief descriptions are given of the computer algebra computations that arise when working with various operators and their actions.
An application of multigrid methods for a discrete elastic model for epitaxial systems
International Nuclear Information System (INIS)
Caflisch, R.E.; Lee, Y.-J.; Shu, S.; Xiao, Y.-X.; Xu, J.
2006-01-01
We apply an efficient and fast algorithm to simulate the atomistic strain model for epitaxial systems, recently introduced by Schindler et al. [Phys. Rev. B 67, 075316 (2003)]. The discrete effects in this lattice statics model are crucial for proper simulation of the influence of strain for thin film epitaxial growth, but the size of the atomistic systems of interest is in general quite large and hence the solution of the discrete elastic equations is a considerable numerical challenge. In this paper, we construct an algebraic multigrid method suitable for efficient solution of the large scale discrete strain model. Using this method, simulations are performed for several representative physical problems, including an infinite periodic step train, a layered nanocrystal, and a system of quantum dots. The results demonstrate the effectiveness and robustness of the method and show that the method attains optimal convergence properties, regardless of the problem size, the geometry and the physical parameters. The effects of substrate depth and of invariance due to traction-free boundary conditions are assessed. For a system of quantum dots, the simulated strain energy density supports the observations that trench formation near the dots provides strain relief
Clark, M. A.; Jung, Chulwoo; Lehner, Christoph
2018-03-01
We present a Lanczos algorithm utilizing multiple grids that reduces the memory requirements both on disk and in working memory by one order of magnitude for RBC/UKQCD's 48I and 64I ensembles at the physical pion mass. The precision of the resulting eigenvectors is on par with exact deflation.
Directory of Open Access Journals (Sweden)
Clark M. A.
2018-01-01
Full Text Available We present a Lanczos algorithm utilizing multiple grids that reduces the memory requirements both on disk and in working memory by one order of magnitude for RBC/UKQCD’s 48I and 64I ensembles at the physical pion mass. The precision of the resulting eigenvectors is on par with exact deflation.
Algebraic partial Boolean algebras
International Nuclear Information System (INIS)
Smith, Derek
2003-01-01
Partial Boolean algebras, first studied by Kochen and Specker in the 1960s, provide the structure for Bell-Kochen-Specker theorems which deny the existence of non-contextual hidden variable theories. In this paper, we study partial Boolean algebras which are 'algebraic' in the sense that their elements have coordinates in an algebraic number field. Several of these algebras have been discussed recently in a debate on the validity of Bell-Kochen-Specker theorems in the context of finite precision measurements. The main result of this paper is that every algebraic finitely-generated partial Boolean algebra B(T) is finite when the underlying space H is three-dimensional, answering a question of Kochen and showing that Conway and Kochen's infinite algebraic partial Boolean algebra has minimum dimension. This result contrasts the existence of an infinite (non-algebraic) B(T) generated by eight elements in an abstract orthomodular lattice of height 3. We then initiate a study of higher-dimensional algebraic partial Boolean algebras. First, we describe a restriction on the determinants of the elements of B(T) that are generated by a given set T. We then show that when the generating set T consists of the rays spanning the minimal vectors in a real irreducible root lattice, B(T) is infinite just if that root lattice has an A 5 sublattice. Finally, we characterize the rays of B(T) when T consists of the rays spanning the minimal vectors of the root lattice E 8
Singh, S; Modi, S; Bagga, D; Kaur, P; Shankar, L R; Khushu, S
2013-03-01
The present study aimed to investigate whether brain morphological differences exist between adult hypothyroid subjects and age-matched controls using voxel-based morphometry (VBM) with diffeomorphic anatomic registration via an exponentiated lie algebra algorithm (DARTEL) approach. High-resolution structural magnetic resonance images were taken in ten healthy controls and ten hypothyroid subjects. The analysis was conducted using statistical parametric mapping. The VBM study revealed a reduction in grey matter volume in the left postcentral gyrus and cerebellum of hypothyroid subjects compared to controls. A significant reduction in white matter volume was also found in the cerebellum, right inferior and middle frontal gyrus, right precentral gyrus, right inferior occipital gyrus and right temporal gyrus of hypothyroid patients compared to healthy controls. Moreover, no meaningful cluster for greater grey or white matter volume was obtained in hypothyroid subjects compared to controls. Our study is the first VBM study of hypothyroidism in an adult population and suggests that, compared to controls, this disorder is associated with differences in brain morphology in areas corresponding to known functional deficits in attention, language, motor speed, visuospatial processing and memory in hypothyroidism. © 2012 British Society for Neuroendocrinology.
NONLINEAR MULTIGRID SOLVER EXPLOITING AMGe COARSE SPACES WITH APPROXIMATION PROPERTIES
Energy Technology Data Exchange (ETDEWEB)
Christensen, Max La Cour [Technical Univ. of Denmark, Lyngby (Denmark); Villa, Umberto E. [Univ. of Texas, Austin, TX (United States); Engsig-Karup, Allan P. [Technical Univ. of Denmark, Lyngby (Denmark); Vassilevski, Panayot S. [Lawrence Livermore National Lab. (LLNL), Livermore, CA (United States)
2016-01-22
The paper introduces a nonlinear multigrid solver for mixed nite element discretizations based on the Full Approximation Scheme (FAS) and element-based Algebraic Multigrid (AMGe). The main motivation to use FAS for unstruc- tured problems is the guaranteed approximation property of the AMGe coarse spaces that were developed recently at Lawrence Livermore National Laboratory. These give the ability to derive stable and accurate coarse nonlinear discretization problems. The previous attempts (including ones with the original AMGe method, [5, 11]), were less successful due to lack of such good approximation properties of the coarse spaces. With coarse spaces with approximation properties, our FAS approach on un- structured meshes should be as powerful/successful as FAS on geometrically re ned meshes. For comparison, Newton's method and Picard iterations with an inner state-of-the-art linear solver is compared to FAS on a nonlinear saddle point problem with applications to porous media ow. It is demonstrated that FAS is faster than Newton's method and Picard iterations for the experiments considered here. Due to the guaranteed approximation properties of our AMGe, the coarse spaces are very accurate, providing a solver with the potential for mesh-independent convergence on general unstructured meshes.
Multi-grid and ICCG for problems with interfaces
International Nuclear Information System (INIS)
Dendy, J.E.; Hyman, J.M.
1980-01-01
Computation times for the multi-grid (MG) algorithm, the incomplete Cholesky conjugate gradient (ICCG) algorithm [J. Comp. Phys. 26, 43-65 (1978); Math. Comp. 31, 148-162 (1977)], and the modified ICCG (MICCG) algorithm [BIT 18, 142-156 (1978)] to solve elliptic partial differential equations are compared. The MICCG and ICCG algorithms are more robust than the MG for general positive definite systems. A major advantage of the MG algorithm is that the structure of the problem can be exploited to reduce the solution time significantly. Five example problems are discussed. For problems with little structure and for one-shot calculations ICCG is recommended over MG, and MICCG, over ICCG. For problems that are done many times, it is worth investing the effort to study methods like MG. 1 table
The multigrid preconditioned conjugate gradient method
Tatebe, Osamu
1993-01-01
A multigrid preconditioned conjugate gradient method (MGCG method), which uses the multigrid method as a preconditioner of the PCG method, is proposed. The multigrid method has inherent high parallelism and improves convergence of long wavelength components, which is important in iterative methods. By using this method as a preconditioner of the PCG method, an efficient method with high parallelism and fast convergence is obtained. First, it is considered a necessary condition of the multigrid preconditioner in order to satisfy requirements of a preconditioner of the PCG method. Next numerical experiments show a behavior of the MGCG method and that the MGCG method is superior to both the ICCG method and the multigrid method in point of fast convergence and high parallelism. This fast convergence is understood in terms of the eigenvalue analysis of the preconditioned matrix. From this observation of the multigrid preconditioner, it is realized that the MGCG method converges in very few iterations and the multigrid preconditioner is a desirable preconditioner of the conjugate gradient method.
International Nuclear Information System (INIS)
Calmet, J.
1982-01-01
A survey of applications based either on fundamental algorithms in computer algebra or on the use of a computer algebra system is presented. Recent work in biology, chemistry, physics, mathematics and computer science is discussed. In particular, applications in high energy physics (quantum electrodynamics), celestial mechanics and general relativity are reviewed. (Auth.)
Evaluation of global synchronization for iterative algebra algorithms on many-core
ul Hasan Khan, Ayaz; Al-Mouhamed, Mayez; Firdaus, Lutfi A.
2015-01-01
© 2015 IEEE. Massively parallel computing is applied extensively in various scientific and engineering domains. With the growing interest in many-core architectures and due to the lack of explicit support for inter-block synchronization specifically in GPUs, synchronization becomes necessary to minimize inter-block communication time. In this paper, we have proposed two new inter-block synchronization techniques: 1) Relaxed Synchronization, and 2) Block-Query Synchronization. These schemes are used in implementing numerical iterative solvers where computation/communication overlapping is one used optimization to enhance application performance. We have evaluated and analyzed the performance of the proposed synchronization techniques using Jacobi Iterative Solver in comparison to the state of the art inter-block lock-free synchronization techniques. We have achieved about 1-8% performance improvement in terms of execution time over lock-free synchronization depending on the problem size and the number of thread blocks. We have also evaluated the proposed algorithm on GPU and MIC architectures and obtained about 8-26% performance improvement over the barrier synchronization available in OpenMP programming environment depending on the problem size and number of cores used.
Evaluation of global synchronization for iterative algebra algorithms on many-core
ul Hasan Khan, Ayaz
2015-06-01
© 2015 IEEE. Massively parallel computing is applied extensively in various scientific and engineering domains. With the growing interest in many-core architectures and due to the lack of explicit support for inter-block synchronization specifically in GPUs, synchronization becomes necessary to minimize inter-block communication time. In this paper, we have proposed two new inter-block synchronization techniques: 1) Relaxed Synchronization, and 2) Block-Query Synchronization. These schemes are used in implementing numerical iterative solvers where computation/communication overlapping is one used optimization to enhance application performance. We have evaluated and analyzed the performance of the proposed synchronization techniques using Jacobi Iterative Solver in comparison to the state of the art inter-block lock-free synchronization techniques. We have achieved about 1-8% performance improvement in terms of execution time over lock-free synchronization depending on the problem size and the number of thread blocks. We have also evaluated the proposed algorithm on GPU and MIC architectures and obtained about 8-26% performance improvement over the barrier synchronization available in OpenMP programming environment depending on the problem size and number of cores used.
Multi-grid Beam and Warming scheme for the simulation of unsteady ...
African Journals Online (AJOL)
In this paper, a multi-grid algorithm is applied to a large-scale block matrix that is produced from a Beam and Warming scheme. The Beam and Warming scheme is used in the simulation of unsteady flow in an open channel. The Gauss-Seidel block-wise iteration method is used for a smoothing process with a few iterations.
Multigrid on unstructured grids using an auxiliary set of structured grids
Energy Technology Data Exchange (ETDEWEB)
Douglas, C.C.; Malhotra, S.; Schultz, M.H. [Yale Univ., New Haven, CT (United States)
1996-12-31
Unstructured grids do not have a convenient and natural multigrid framework for actually computing and maintaining a high floating point rate on standard computers. In fact, just the coarsening process is expensive for many applications. Since unstructured grids play a vital role in many scientific computing applications, many modifications have been proposed to solve this problem. One suggested solution is to map the original unstructured grid onto a structured grid. This can be used as a fine grid in a standard multigrid algorithm to precondition the original problem on the unstructured grid. We show that unless extreme care is taken, this mapping can lead to a system with a high condition number which eliminates the usefulness of the multigrid method. Theorems with lower and upper bounds are provided. Simple examples show that the upper bounds are sharp.
Multigrid solution of diffusion equations on distributed memory multiprocessor systems
International Nuclear Information System (INIS)
Finnemann, H.
1988-01-01
The subject is the solution of partial differential equations for simulation of the reactor core on high-performance computers. The parallelization and implementation of nodal multigrid diffusion algorithms on array and ring configurations of the DIRMU multiprocessor system is outlined. The particular iteration scheme employed in the nodal expansion method appears similarly efficient in serial and parallel environments. The combination of modern multi-level techniques with innovative hardware (vector-multiprocessor systems) provides powerful tools needed for real time simulation of physical systems. The parallel efficiencies range from 70 to 90%. The same performance is estimated for large problems on large multiprocessor systems being designed at present. (orig.) [de
Summary Report: Multigrid for Systems of Elliptic PDEs
Energy Technology Data Exchange (ETDEWEB)
Lee, Barry [Lawrence Livermore National Lab. (LLNL), Livermore, CA (United States)
2016-11-17
We are interested in determining if multigrid can be effectively applied to the system. The conclusion that I seem to be drawn to is that it is impossible to develop a blackbox multigrid solver for these general systems. Analysis of the system of PDEs must be conducted first to determine pre-processing procedures on the continuous problem before applying a multigrid method. Determining this pre-processing is currently not incorporated in black-box multigrid strategies. Nevertheless, we characterize some system features that will make the system more amenable to multigrid approaches, techniques that may lead to more amenable systems, and multigrid procedures that are generally more appropriate for these systems.
Analysis and development of stochastic multigrid methods in lattice field theory
International Nuclear Information System (INIS)
Grabenstein, M.
1994-01-01
We study the relation between the dynamical critical behavior and the kinematics of stochastic multigrid algorithms. The scale dependence of acceptance rates for nonlocal Metropolis updates is analyzed with the help of an approximation formula. A quantitative study of the kinematics of multigrid algorithms in several interacting models is performed. We find that for a critical model with Hamiltonian H(Φ) absence of critical slowing down can only be expected if the expansion of (H(Φ+ψ)) in terms of the shift ψ contains no relevant term (mass term). The predictions of this rule was verified in a multigrid Monte Carlo simulation of the Sine Gordon model in two dimensions. Our analysis can serve as a guideline for the development of new algorithms: We propose a new multigrid method for nonabelian lattice gauge theory, the time slice blocking. For SU(2) gauge fields in two dimensions, critical slowing down is almost completely eliminated by this method, in accordance with the theoretical prediction. The generalization of the time slice blocking to SU(2) in four dimensions is investigated analytically and by numerical simulations. Compared to two dimensions, the local disorder in the four dimensional gauge field leads to kinematical problems. (orig.)
Extreme simplification and rendering of point sets using algebraic multigrid
Reniers, D.; Telea, A.C.
2009-01-01
We present a novel approach for extreme simplification of point set models, in the context of real-time rendering. Point sets are often rendered using simple point primitives, such as oriented discs. However, this requires using many primitives to render even moderately simple shapes. Often, one
Extreme Simplification and Rendering of Point Sets using Algebraic Multigrid
Reniers, Dennie; Telea, Alexandru
2005-01-01
We present a novel approach for extreme simplification of point set models in the context of real-time rendering. Point sets are often rendered using simple point primitives, such as oriented discs. However efficient, simple primitives are less effective in approximating large surface areas. A large
Lefschetz, Solomon
2005-01-01
An introduction to algebraic geometry and a bridge between its analytical-topological and algebraical aspects, this text for advanced undergraduate students is particularly relevant to those more familiar with analysis than algebra. 1953 edition.
International Nuclear Information System (INIS)
Garcia, R.L.
1983-11-01
The Grassmann algebra is presented briefly. Exponential and logarithm of matrices functions, whose elements belong to this algebra, are studied with the help of the SCHOONSCHIP and REDUCE 2 algebraic manipulators. (Author) [pt
A Pseudo-Temporal Multi-Grid Relaxation Scheme for Solving the Parabolized Navier-Stokes Equations
White, J. A.; Morrison, J. H.
1999-01-01
A multi-grid, flux-difference-split, finite-volume code, VULCAN, is presented for solving the elliptic and parabolized form of the equations governing three-dimensional, turbulent, calorically perfect and non-equilibrium chemically reacting flows. The space marching algorithms developed to improve convergence rate and or reduce computational cost are emphasized. The algorithms presented are extensions to the class of implicit pseudo-time iterative, upwind space-marching schemes. A full approximate storage, full multi-grid scheme is also described which is used to accelerate the convergence of a Gauss-Seidel relaxation method. The multi-grid algorithm is shown to significantly improve convergence on high aspect ratio grids.
Multigrid Methods for EHL Problems
Nurgat, Elyas; Berzins, Martin
1996-01-01
In many bearings and contacts, forces are transmitted through thin continuous fluid films which separate two contacting elements. Objects in contact are normally subjected to friction and wear which can be reduced effectively by using lubricants. If the lubricant film is sufficiently thin to prevent the opposing solids from coming into contact and carries the entire load, then we have hydrodynamic lubrication, where the lubricant film is determined by the motion and geometry of the solids. However, for loaded contacts of low geometrical conformity, such as gears, rolling contact bearings and cams, this is not the case due to high pressures and this is referred to as Elasto-Hydrodynamic Lubrication (EHL) In EHL, elastic deformation of the contacting elements and the increase in fluid viscosity with pressure are very significant and cannot be ignored. Since the deformation results in changing the geometry of the lubricating film, which in turn determines the pressure distribution, an EHL mathematical model must simultaneously satisfy the complex elasticity (integral) and the Reynolds lubrication (differential) equations. The nonlinear and coupled nature of the two equations makes numerical calculations computationally intensive. This is especially true for highly loaded problems found in practice. One novel feature of these problems is that the solution may exhibit sharp pressure spikes in the outlet region. To this date both finite element and finite difference methods have been used to solve EHL problems with perhaps greater emphasis on the use of the finite difference approach. In both cases, a major computational difficulty is ensuring convergence of the nonlinear equations solver to a steady state solution. Two successful methods for achieving this are direct iteration and multigrid methods. Direct iteration methods (e.g Gauss Seidel) have long been used in conjunction with finite difference discretizations on regular meshes. Perhaps one of the best examples of
Vertex algebras and algebraic curves
Frenkel, Edward
2004-01-01
Vertex algebras are algebraic objects that encapsulate the concept of operator product expansion from two-dimensional conformal field theory. Vertex algebras are fast becoming ubiquitous in many areas of modern mathematics, with applications to representation theory, algebraic geometry, the theory of finite groups, modular functions, topology, integrable systems, and combinatorics. This book is an introduction to the theory of vertex algebras with a particular emphasis on the relationship with the geometry of algebraic curves. The notion of a vertex algebra is introduced in a coordinate-independent way, so that vertex operators become well defined on arbitrary smooth algebraic curves, possibly equipped with additional data, such as a vector bundle. Vertex algebras then appear as the algebraic objects encoding the geometric structure of various moduli spaces associated with algebraic curves. Therefore they may be used to give a geometric interpretation of various questions of representation theory. The book co...
African Journals Online (AJOL)
Tadesse
In this paper we introduce the concept of implicative algebras which is an equivalent definition of lattice implication algebra of Xu (1993) and further we prove that it is a regular Autometrized. Algebra. Further we remark that the binary operation → on lattice implicative algebra can never be associative. Key words: Implicative ...
Villarreal, Rafael
2015-01-01
The book stresses the interplay between several areas of pure and applied mathematics, emphasizing the central role of monomial algebras. It unifies the classical results of commutative algebra with central results and notions from graph theory, combinatorics, linear algebra, integer programming, and combinatorial optimization. The book introduces various methods to study monomial algebras and their presentation ideals, including Stanley-Reisner rings, subrings and blowup algebra-emphasizing square free quadratics, hypergraph clutters, and effective computational methods.
On the multi-level solution algorithm for Markov chains
Energy Technology Data Exchange (ETDEWEB)
Horton, G. [Univ. of Erlangen, Nuernberg (Germany)
1996-12-31
We discuss the recently introduced multi-level algorithm for the steady-state solution of Markov chains. The method is based on the aggregation principle, which is well established in the literature. Recursive application of the aggregation yields a multi-level method which has been shown experimentally to give results significantly faster than the methods currently in use. The algorithm can be reformulated as an algebraic multigrid scheme of Galerkin-full approximation type. The uniqueness of the scheme stems from its solution-dependent prolongation operator which permits significant computational savings in the evaluation of certain terms. This paper describes the modeling of computer systems to derive information on performance, measured typically as job throughput or component utilization, and availability, defined as the proportion of time a system is able to perform a certain function in the presence of component failures and possibly also repairs.
Block-accelerated aggregation multigrid for Markov chains with application to PageRank problems
Shen, Zhao-Li; Huang, Ting-Zhu; Carpentieri, Bruno; Wen, Chun; Gu, Xian-Ming
2018-06-01
Recently, the adaptive algebraic aggregation multigrid method has been proposed for computing stationary distributions of Markov chains. This method updates aggregates on every iterative cycle to keep high accuracies of coarse-level corrections. Accordingly, its fast convergence rate is well guaranteed, but often a large proportion of time is cost by aggregation processes. In this paper, we show that the aggregates on each level in this method can be utilized to transfer the probability equation of that level into a block linear system. Then we propose a Block-Jacobi relaxation that deals with the block system on each level to smooth error. Some theoretical analysis of this technique is presented, meanwhile it is also adapted to solve PageRank problems. The purpose of this technique is to accelerate the adaptive aggregation multigrid method and its variants for solving Markov chains and PageRank problems. It also attempts to shed some light on new solutions for making aggregation processes more cost-effective for aggregation multigrid methods. Numerical experiments are presented to illustrate the effectiveness of this technique.
Polishchuk, Alexander
2005-01-01
Quadratic algebras, i.e., algebras defined by quadratic relations, often occur in various areas of mathematics. One of the main problems in the study of these (and similarly defined) algebras is how to control their size. A central notion in solving this problem is the notion of a Koszul algebra, which was introduced in 1970 by S. Priddy and then appeared in many areas of mathematics, such as algebraic geometry, representation theory, noncommutative geometry, K-theory, number theory, and noncommutative linear algebra. The book offers a coherent exposition of the theory of quadratic and Koszul algebras, including various definitions of Koszulness, duality theory, Poincar�-Birkhoff-Witt-type theorems for Koszul algebras, and the Koszul deformation principle. In the concluding chapter of the book, they explain a surprising connection between Koszul algebras and one-dependent discrete-time stochastic processes.
The relation between quantum W algebras and Lie algebras
International Nuclear Information System (INIS)
Boer, J. de; Tjin, T.
1994-01-01
By quantizing the generalized Drinfeld-Sokolov reduction scheme for arbitrary sl 2 embeddings we show that a large set W of quantum W algebras can be viewed as (BRST) cohomologies of affine Lie algebras. The set W contains many known W algebras such as W N and W 3 (2) . Our formalism yields a completely algorithmic method for calculating the W algebra generators and their operator product expansions, replacing the cumbersome construction of W algebras as commutants of screening operators. By generalizing and quantizing the Miura transformation we show that any W algebra in W can be embedded into the universal enveloping algebra of a semisimple affine Lie algebra which is, up to shifts in level, isomorphic to a subalgebra of the original affine algebra. Therefore any realization of this semisimple affine Lie algebra leads to a realization of the W algebra. In particular, one obtains in this way a general and explicit method for constructing the free field realizations and Fock resolutions for all algebras in W. Some examples are explicitly worked out. (orig.)
Experiences using multigrid for geothermal simulation
Energy Technology Data Exchange (ETDEWEB)
Bullivant, D.P.; O`Sullivan, M.J. [Univ. of Auckland (New Zealand); Yang, Z. [Univ. of New South Wales (Australia)
1995-03-01
Experiences of applying multigrid to the calculation of natural states for geothermal simulations are discussed. The modelling of natural states was chosen for this study because they can take a long time to compute and the computation is often dominated by the development of phase change boundaries that take up a small region in the simulation. For the first part of this work a modified version of TOUGH was used for 2-D vertical problems. A {open_quotes}test-bed{close_quotes} program is now being used to investigate some of the problems encountered with implementing multigrid. This is ongoing work. To date, there have been some encouraging but not startling results.
A multigrid method for variational inequalities
Energy Technology Data Exchange (ETDEWEB)
Oliveira, S.; Stewart, D.E.; Wu, W.
1996-12-31
Multigrid methods have been used with great success for solving elliptic partial differential equations. Penalty methods have been successful in solving finite-dimensional quadratic programs. In this paper these two techniques are combined to give a fast method for solving obstacle problems. A nonlinear penalized problem is solved using Newton`s method for large values of a penalty parameter. Multigrid methods are used to solve the linear systems in Newton`s method. The overall numerical method developed is based on an exterior penalty function, and numerical results showing the performance of the method have been obtained.
Lavery, N.; Taylor, C.
1999-07-01
Multigrid and iterative methods are used to reduce the solution time of the matrix equations which arise from the finite element (FE) discretisation of the time-independent equations of motion of the incompressible fluid in turbulent motion. Incompressible flow is solved by using the method of reduce interpolation for the pressure to satisfy the Brezzi-Babuska condition. The k-l model is used to complete the turbulence closure problem. The non-symmetric iterative matrix methods examined are the methods of least squares conjugate gradient (LSCG), biconjugate gradient (BCG), conjugate gradient squared (CGS), and the biconjugate gradient squared stabilised (BCGSTAB). The multigrid algorithm applied is based on the FAS algorithm of Brandt, and uses two and three levels of grids with a V-cycling schedule. These methods are all compared to the non-symmetric frontal solver. Copyright
An Optimal Order Nonnested Mixed Multigrid Method for Generalized Stokes Problems
Deng, Qingping
1996-01-01
A multigrid algorithm is developed and analyzed for generalized Stokes problems discretized by various nonnested mixed finite elements within a unified framework. It is abstractly proved by an element-independent analysis that the multigrid algorithm converges with an optimal order if there exists a 'good' prolongation operator. A technique to construct a 'good' prolongation operator for nonnested multilevel finite element spaces is proposed. Its basic idea is to introduce a sequence of auxiliary nested multilevel finite element spaces and define a prolongation operator as a composite operator of two single grid level operators. This makes not only the construction of a prolongation operator much easier (the final explicit forms of such prolongation operators are fairly simple), but the verification of the approximate properties for prolongation operators is also simplified. Finally, as an application, the framework and technique is applied to seven typical nonnested mixed finite elements.
Goodstein, R L
2007-01-01
This elementary treatment by a distinguished mathematician employs Boolean algebra as a simple medium for introducing important concepts of modern algebra. Numerous examples appear throughout the text, plus full solutions.
On the fixed-stress split scheme as smoother in multigrid methods for coupling flow and geomechanics
F.J. Gaspar Lorenz (Franscisco); C. Rodrigo (Carmen)
2017-01-01
textabstractThe fixed-stress split method has been widely used as solution method in the coupling of flow and geomechanics. In this work, we analyze the behavior of an inexact version of this algorithm as smoother within a geometric multigrid method, in order to obtain an efficient monolithic solver
Hirata, So; Doran, Alexander E; Knowles, Peter J; Ortiz, J V
2017-07-28
A thorough analytical and numerical characterization of the whole perturbation series of one-particle many-body Green's function (MBGF) theory is presented in a pedagogical manner. Three distinct but equivalent algebraic (first-quantized) recursive definitions of the perturbation series of the Green's function are derived, which can be combined with the well-known recursion for the self-energy. Six general-order algorithms of MBGF are developed, each implementing one of the three recursions, the ΔMPn method (where n is the perturbation order) [S. Hirata et al., J. Chem. Theory Comput. 11, 1595 (2015)], the automatic generation and interpretation of diagrams, or the numerical differentiation of the exact Green's function with a perturbation-scaled Hamiltonian. They all display the identical, nondivergent perturbation series except ΔMPn, which agrees with MBGF in the diagonal and frequency-independent approximations at 1≤n≤3 but converges at the full-configuration-interaction (FCI) limit at n=∞ (unless it diverges). Numerical data of the perturbation series are presented for Koopmans and non-Koopmans states to quantify the rate of convergence towards the FCI limit and the impact of the diagonal, frequency-independent, or ΔMPn approximation. The diagrammatic linkedness and thus size-consistency of the one-particle Green's function and self-energy are demonstrated at any perturbation order on the basis of the algebraic recursions in an entirely time-independent (frequency-domain) framework. The trimming of external lines in a one-particle Green's function to expose a self-energy diagram and the removal of reducible diagrams are also justified mathematically using the factorization theorem of Frantz and Mills. Equivalence of ΔMPn and MBGF in the diagonal and frequency-independent approximations at 1≤n≤3 is algebraically proven, also ascribing the differences at n = 4 to the so-called semi-reducible and linked-disconnected diagrams.
Efficient multigrid computation of steady hypersonic flows
Koren, B.; Hemker, P.W.; Murthy, T.K.S.
1991-01-01
In steady hypersonic flow computations, Newton iteration as a local relaxation procedure and nonlinear multigrid iteration as an acceleration procedure may both easily fail. In the present chapter, same remedies are presented for overcoming these problems. The equations considered are the steady,
The multigrid method for reactor calculations
International Nuclear Information System (INIS)
Douglas, S.R.
1991-07-01
Iterative solutions to linear systems of equations are discussed. The emphasis is on the concepts that affect convergence rates of these solution methods. The multigrid method is described, including the smoothing property, restriction, and prolongation. A simple example is used to illustrate the ideas
Algebraic curves and cryptography
Murty, V Kumar
2010-01-01
It is by now a well-known paradigm that public-key cryptosystems can be built using finite Abelian groups and that algebraic geometry provides a supply of such groups through Abelian varieties over finite fields. Of special interest are the Abelian varieties that are Jacobians of algebraic curves. All of the articles in this volume are centered on the theme of point counting and explicit arithmetic on the Jacobians of curves over finite fields. The topics covered include Schoof's \\ell-adic point counting algorithm, the p-adic algorithms of Kedlaya and Denef-Vercauteren, explicit arithmetic on
Jordan algebras versus C*- algebras
International Nuclear Information System (INIS)
Stormer, E.
1976-01-01
The axiomatic formulation of quantum mechanics and the problem of whether the observables form self-adjoint operators on a Hilbert space, are discussed. The relation between C*- algebras and Jordan algebras is studied using spectral theory. (P.D.)
Templates for Linear Algebra Problems
Bai, Z.; Day, D.; Demmel, J.; Dongarra, J.; Gu, M.; Ruhe, A.; Vorst, H.A. van der
1995-01-01
The increasing availability of advanced-architecture computers is having a very signicant eect on all spheres of scientic computation, including algorithm research and software development in numerical linear algebra. Linear algebra {in particular, the solution of linear systems of equations and
Scalable multi-grid preconditioning techniques for the even-parity S_N solver in UNIC
International Nuclear Information System (INIS)
Mahadevan, Vijay S.; Smith, Michael A.
2011-01-01
The Even-parity neutron transport equation with FE-S_N discretization is solved traditionally using SOR preconditioned CG method at the lowest level of iterations in order to compute the criticality in reactor analysis problems. The use of high order isoparametric finite elements prohibits the formation of the discrete operator explicitly due to memory constraints in peta scale architectures. Hence, a h-p multi-grid preconditioner based on linear tessellation of the higher order mesh is introduced here for the space-angle system and compared against SOR and Algebraic MG black-box solvers. The performance and scalability of the multi-grid scheme was determined for two test problems and found to be competitive in terms of both computational time and memory requirements. The implementation of this preconditioner in an even-parity solver like UNIC from ANL can further enable high fidelity calculations in a scalable manner on peta flop machines. (author)
Directory of Open Access Journals (Sweden)
Naseem Cassim
2017-02-01
Full Text Available Introduction: CD4 testing in South Africa is based on an integrated tiered service delivery model that matches testing demand with capacity. The National Health Laboratory Service has predominantly implemented laboratory-based CD4 testing. Coverage gaps, over-/under-capacitation and optimal placement of point-of-care (POC testing sites need investigation. Objectives: We assessed the impact of relational algebraic capacitated location (RACL algorithm outcomes on the allocation of laboratory and POC testing sites. Methods: The RACL algorithm was developed to allocate laboratories and POC sites to ensure coverage using a set coverage approach for a defined travel time (T. The algorithm was repeated for three scenarios (A: T = 4; B: T = 3; C: T = 2 hours. Drive times for a representative sample of health facility clusters were used to approximate T. Outcomes included allocation of testing sites, Euclidian distances and test volumes. Additional analysis included platform distribution and space requirement assessment. Scenarios were reported as fusion table maps. Results: Scenario A would offer a fully-centralised approach with 15 CD4 laboratories without any POC testing. A significant increase in volumes would result in a four-fold increase at busier laboratories. CD4 laboratories would increase to 41 in scenario B and 61 in scenario C. POC testing would be offered at two sites in scenario B and 20 sites in scenario C. Conclusion: The RACL algorithm provides an objective methodology to address coverage gaps through the allocation of CD4 laboratories and POC sites for a given T. The algorithm outcomes need to be assessed in the context of local conditions.
International Nuclear Information System (INIS)
Belliard, M.; Grandotto, M.
2003-01-01
In the framework of the two-phase fluid simulations of the steam generators of pressurized water nuclear reactors, we present in this paper a geometric version of a pseudo-Full MultiGrid (pseudo- FMG) Full Approximation Storage (FAS) preconditioning of balance equations in the GENEPI code. In our application, the 3D steady state flow is reached by a transient computation using a semi-implicit fractional step algorithm for the averaged two-phase mixture balance equations (mass, momentum and energy for the secondary flow). Our application, running on workstation clusters, is based on a CEA code-linker and the PVM package. The difficulties to apply the geometric FAS multigrid method to the momentum and mass balance equations are addressed. The use of a sequential pseudo-FMG FAS twogrid method for both energy and mass/momentum balance equations, using dynamic multigrid cycles, leads to perceptibly improvements in the computation convergences. An original parallel red-black pseudo-FMG FAS three-grid algorithm is presented too. The numerical tests (steam generator mockup simulations) underline the sizable increase in speed of convergence of the computations, essentially for the ones involving a large number of freedom degrees (about 100 thousand cells). The two-phase mixture balance equation residuals are quickly reduced: the reached speed-up stands between 2 and 3 following the number of grids. The effects on the convergence behavior of the numerical parameters are investigated
Energy Technology Data Exchange (ETDEWEB)
Gjesdal, Thor
1997-12-31
This thesis discusses the development and application of efficient numerical methods for the simulation of fluid flows, in particular the flow of incompressible fluids. The emphasis is on practical aspects of algorithm development and on application of the methods either to linear scalar model equations or to the non-linear incompressible Navier-Stokes equations. The first part deals with cell centred multigrid methods and linear correction scheme and presents papers on (1) generalization of the method to arbitrary sized grids for diffusion problems, (2) low order method for advection-diffusion problems, (3) attempt to extend the basic method to advection-diffusion problems, (4) Fourier smoothing analysis of multicolour relaxation schemes, and (5) analysis of high-order discretizations for advection terms. The second part discusses a multigrid based on pressure correction methods, non-linear full approximation scheme, and papers on (1) systematic comparison of the performance of different pressure correction smoothers and some other algorithmic variants, low to moderate Reynolds numbers, and (2) systematic study of implementation strategies for high order advection schemes, high-Re flow. An appendix contains Fortran 90 data structures for multigrid development. 160 refs., 26 figs., 22 tabs.
The Closest Point Method and Multigrid Solvers for Elliptic Equations on Surfaces
Chen, Yujia
2015-01-01
© 2015 Society for Industrial and Applied Mathematics. Elliptic partial differential equations are important from both application and analysis points of view. In this paper we apply the closest point method to solve elliptic equations on general curved surfaces. Based on the closest point representation of the underlying surface, we formulate an embedding equation for the surface elliptic problem, then discretize it using standard finite differences and interpolation schemes on banded but uniform Cartesian grids. We prove the convergence of the difference scheme for the Poisson\\'s equation on a smooth closed curve. In order to solve the resulting large sparse linear systems, we propose a specific geometric multigrid method in the setting of the closest point method. Convergence studies in both the accuracy of the difference scheme and the speed of the multigrid algorithm show that our approaches are effective.
Multigrid Finite Element Method in Calculation of 3D Homogeneous and Composite Solids
Directory of Open Access Journals (Sweden)
A.D. Matveev
2016-12-01
Full Text Available In the present paper, a method of multigrid finite elements to calculate elastic three-dimensional homogeneous and composite solids under static loading has been suggested. The method has been developed based on the finite element method algorithms using homogeneous and composite three-dimensional multigrid finite elements (MFE. The procedures for construction of MFE of both rectangular parallelepiped and complex shapes have been shown. The advantages of MFE are that they take into account, following the rules of the microapproach, heterogeneous and microhomogeneous structures of the bodies, describe the three-dimensional stress-strain state (without any simplifying hypotheses in homogeneous and composite solids, as well as generate small dimensional discrete models and numerical solutions with a high accuracy.
Ford, Timothy J
2017-01-01
This book presents a comprehensive introduction to the theory of separable algebras over commutative rings. After a thorough introduction to the general theory, the fundamental roles played by separable algebras are explored. For example, Azumaya algebras, the henselization of local rings, and Galois theory are rigorously introduced and treated. Interwoven throughout these applications is the important notion of étale algebras. Essential connections are drawn between the theory of separable algebras and Morita theory, the theory of faithfully flat descent, cohomology, derivations, differentials, reflexive lattices, maximal orders, and class groups. The text is accessible to graduate students who have finished a first course in algebra, and it includes necessary foundational material, useful exercises, and many nontrivial examples.
Elements of algebraic coding systems
Cardoso da Rocha, Jr, Valdemar
2014-01-01
Elements of Algebraic Coding Systems is an introductory text to algebraic coding theory. In the first chapter, you'll gain inside knowledge of coding fundamentals, which is essential for a deeper understanding of state-of-the-art coding systems. This book is a quick reference for those who are unfamiliar with this topic, as well as for use with specific applications such as cryptography and communication. Linear error-correcting block codes through elementary principles span eleven chapters of the text. Cyclic codes, some finite field algebra, Goppa codes, algebraic decoding algorithms, and applications in public-key cryptography and secret-key cryptography are discussed, including problems and solutions at the end of each chapter. Three appendices cover the Gilbert bound and some related derivations, a derivation of the Mac- Williams' identities based on the probability of undetected error, and two important tools for algebraic decoding-namely, the finite field Fourier transform and the Euclidean algorithm f...
Kifonidis, K.; Müller, E.
2012-08-01
Aims: We describe and study a family of new multigrid iterative solvers for the multidimensional, implicitly discretized equations of hydrodynamics. Schemes of this class are free of the Courant-Friedrichs-Lewy condition. They are intended for simulations in which widely differing wave propagation timescales are present. A preferred solver in this class is identified. Applications to some simple stiff test problems that are governed by the compressible Euler equations, are presented to evaluate the convergence behavior, and the stability properties of this solver. Algorithmic areas are determined where further work is required to make the method sufficiently efficient and robust for future application to difficult astrophysical flow problems. Methods: The basic equations are formulated and discretized on non-orthogonal, structured curvilinear meshes. Roe's approximate Riemann solver and a second-order accurate reconstruction scheme are used for spatial discretization. Implicit Runge-Kutta (ESDIRK) schemes are employed for temporal discretization. The resulting discrete equations are solved with a full-coarsening, non-linear multigrid method. Smoothing is performed with multistage-implicit smoothers. These are applied here to the time-dependent equations by means of dual time stepping. Results: For steady-state problems, our results show that the efficiency of the present approach is comparable to the best implicit solvers for conservative discretizations of the compressible Euler equations that can be found in the literature. The use of red-black as opposed to symmetric Gauss-Seidel iteration in the multistage-smoother is found to have only a minor impact on multigrid convergence. This should enable scalable parallelization without having to seriously compromise the method's algorithmic efficiency. For time-dependent test problems, our results reveal that the multigrid convergence rate degrades with increasing Courant numbers (i.e. time step sizes). Beyond a
Analysis of multigrid methods on massively parallel computers: Architectural implications
Matheson, Lesley R.; Tarjan, Robert E.
1993-01-01
We study the potential performance of multigrid algorithms running on massively parallel computers with the intent of discovering whether presently envisioned machines will provide an efficient platform for such algorithms. We consider the domain parallel version of the standard V cycle algorithm on model problems, discretized using finite difference techniques in two and three dimensions on block structured grids of size 10(exp 6) and 10(exp 9), respectively. Our models of parallel computation were developed to reflect the computing characteristics of the current generation of massively parallel multicomputers. These models are based on an interconnection network of 256 to 16,384 message passing, 'workstation size' processors executing in an SPMD mode. The first model accomplishes interprocessor communications through a multistage permutation network. The communication cost is a logarithmic function which is similar to the costs in a variety of different topologies. The second model allows single stage communication costs only. Both models were designed with information provided by machine developers and utilize implementation derived parameters. With the medium grain parallelism of the current generation and the high fixed cost of an interprocessor communication, our analysis suggests an efficient implementation requires the machine to support the efficient transmission of long messages, (up to 1000 words) or the high initiation cost of a communication must be significantly reduced through an alternative optimization technique. Furthermore, with variable length message capability, our analysis suggests the low diameter multistage networks provide little or no advantage over a simple single stage communications network.
Linear Algebra and Smarandache Linear Algebra
Vasantha, Kandasamy
2003-01-01
The present book, on Smarandache linear algebra, not only studies the Smarandache analogues of linear algebra and its applications, it also aims to bridge the need for new research topics pertaining to linear algebra, purely in the algebraic sense. We have introduced Smarandache semilinear algebra, Smarandache bilinear algebra and Smarandache anti-linear algebra and their fuzzy equivalents. Moreover, in this book, we have brought out the study of linear algebra and vector spaces over finite p...
Toward textbook multigrid efficiency for fully implicit resistive magnetohydrodynamics
International Nuclear Information System (INIS)
Adams, Mark F.; Samtaney, Ravi; Brandt, Achi
2013-01-01
Multigrid methods can solve some classes of elliptic and parabolic equations to accuracy below the truncation error with a work-cost equivalent to a few residual calculations so-called textbook multigrid efficiency. We investigate methods to solve the system of equations that arise in time dependent magnetohydrodynamics (MHD) simulations with textbook multigrid efficiency. We apply multigrid techniques such as geometric interpolation, full approximate storage, Gauss-Seidel smoothers, and defect correction for fully implicit, nonlinear, second-order finite volume discretizations of MHD. We apply these methods to a standard resistive MHD benchmark problem, the GEM reconnection problem, and add a strong magnetic guide field, which is a critical characteristic of magnetically confined fusion plasmas. We show that our multigrid methods can achieve near textbook efficiency on fully implicit resistive MHD simulations.
Toward textbook multigrid efficiency for fully implicit resistive magnetohydrodynamics
Adams, Mark F.; Samtaney, Ravi; Brandt, Achi
2010-01-01
Multigrid methods can solve some classes of elliptic and parabolic equations to accuracy below the truncation error with a work-cost equivalent to a few residual calculations so-called "textbook" multigrid efficiency. We investigate methods to solve the system of equations that arise in time dependent magnetohydrodynamics (MHD) simulations with textbook multigrid efficiency. We apply multigrid techniques such as geometric interpolation, full approximate storage, Gauss-Seidel smoothers, and defect correction for fully implicit, nonlinear, second-order finite volume discretizations of MHD. We apply these methods to a standard resistive MHD benchmark problem, the GEM reconnection problem, and add a strong magnetic guide field, which is a critical characteristic of magnetically confined fusion plasmas. We show that our multigrid methods can achieve near textbook efficiency on fully implicit resistive MHD simulations. (C) 2010 Elsevier Inc. All rights reserved.
Toward textbook multigrid efficiency for fully implicit resistive magnetohydrodynamics
Adams, Mark F.
2010-09-01
Multigrid methods can solve some classes of elliptic and parabolic equations to accuracy below the truncation error with a work-cost equivalent to a few residual calculations so-called "textbook" multigrid efficiency. We investigate methods to solve the system of equations that arise in time dependent magnetohydrodynamics (MHD) simulations with textbook multigrid efficiency. We apply multigrid techniques such as geometric interpolation, full approximate storage, Gauss-Seidel smoothers, and defect correction for fully implicit, nonlinear, second-order finite volume discretizations of MHD. We apply these methods to a standard resistive MHD benchmark problem, the GEM reconnection problem, and add a strong magnetic guide field, which is a critical characteristic of magnetically confined fusion plasmas. We show that our multigrid methods can achieve near textbook efficiency on fully implicit resistive MHD simulations. (C) 2010 Elsevier Inc. All rights reserved.
Toward textbook multigrid efficiency for fully implicit resistive magnetohydrodynamics
International Nuclear Information System (INIS)
Adams, Mark F.; Samtaney, Ravi; Brandt, Achi
2010-01-01
Multigrid methods can solve some classes of elliptic and parabolic equations to accuracy below the truncation error with a work-cost equivalent to a few residual calculations - so-called 'textbook' multigrid efficiency. We investigate methods to solve the system of equations that arise in time dependent magnetohydrodynamics (MHD) simulations with textbook multigrid efficiency. We apply multigrid techniques such as geometric interpolation, full approximate storage, Gauss-Seidel smoothers, and defect correction for fully implicit, nonlinear, second-order finite volume discretizations of MHD. We apply these methods to a standard resistive MHD benchmark problem, the GEM reconnection problem, and add a strong magnetic guide field, which is a critical characteristic of magnetically confined fusion plasmas. We show that our multigrid methods can achieve near textbook efficiency on fully implicit resistive MHD simulations.
Directory of Open Access Journals (Sweden)
Ivonne Burguet Lago
2018-05-01
Full Text Available ABSTRACT The paper describes a proposal of professional pedagogical performance tests to assess teachers’ role in the process of developing the skill of working with algorithms in Linear Algebra. It aims at devising a testing tool to assess teachers’ performance in the skill-developing process. This tool is a finding of Cuba theory of Advanced Education, systematically used in recent years. The findings include the test design and the illustration of its use in a sample of 22 Linear Algebra teachers during the first term of the 2017-2018 academic year at Informatics Sciences Engineering major. Keywords: ABSTRACT The paper describes a proposal of professional pedagogical performance tests to assess teachers’ role in the process of developing the skill of working with algorithms in Linear Algebra. It aims at devising a testing tool to assess teachers’ performance in the skill-developing process. This tool is a finding of Cuba theory of Advanced Education, systematically used in recent years. The findings include the test design and the illustration of its use in a sample of 22 Linear Algebra teachers during the first term of the 2017-2018 academic year at Informatics Sciences Engineering major.
Constructing canonical bases of quantized enveloping algebras
Graaf, W.A. de
2001-01-01
An algorithm for computing the elements of a given weight of the canonical basis of a quantized enveloping algebra is described. Subsequently, a similar algorithm is presented for computing the canonical basis of a finite-dimensional module.
Garrett, Paul B
2007-01-01
Designed for an advanced undergraduate- or graduate-level course, Abstract Algebra provides an example-oriented, less heavily symbolic approach to abstract algebra. The text emphasizes specifics such as basic number theory, polynomials, finite fields, as well as linear and multilinear algebra. This classroom-tested, how-to manual takes a more narrative approach than the stiff formalism of many other textbooks, presenting coherent storylines to convey crucial ideas in a student-friendly, accessible manner. An unusual feature of the text is the systematic characterization of objects by universal
Kolman, Bernard
1985-01-01
College Algebra, Second Edition is a comprehensive presentation of the fundamental concepts and techniques of algebra. The book incorporates some improvements from the previous edition to provide a better learning experience. It provides sufficient materials for use in the study of college algebra. It contains chapters that are devoted to various mathematical concepts, such as the real number system, the theory of polynomial equations, exponential and logarithmic functions, and the geometric definition of each conic section. Progress checks, warnings, and features are inserted. Every chapter c
Invariants of triangular Lie algebras
International Nuclear Information System (INIS)
Boyko, Vyacheslav; Patera, Jiri; Popovych, Roman
2007-01-01
Triangular Lie algebras are the Lie algebras which can be faithfully represented by triangular matrices of any finite size over the real/complex number field. In the paper invariants ('generalized Casimir operators') are found for three classes of Lie algebras, namely those which are either strictly or non-strictly triangular, and for so-called special upper triangular Lie algebras. Algebraic algorithm of Boyko et al (2006 J. Phys. A: Math. Gen.39 5749 (Preprint math-ph/0602046)), developed further in Boyko et al (2007 J. Phys. A: Math. Theor.40 113 (Preprint math-ph/0606045)), is used to determine the invariants. A conjecture of Tremblay and Winternitz (2001 J. Phys. A: Math. Gen.34 9085), concerning the number of independent invariants and their form, is corroborated
Waterloo Workshop on Computer Algebra
Zima, Eugene; WWCA-2016; Advances in computer algebra : in honour of Sergei Abramov's' 70th birthday
2018-01-01
This book discusses the latest advances in algorithms for symbolic summation, factorization, symbolic-numeric linear algebra and linear functional equations. It presents a collection of papers on original research topics from the Waterloo Workshop on Computer Algebra (WWCA-2016), a satellite workshop of the International Symposium on Symbolic and Algebraic Computation (ISSAC’2016), which was held at Wilfrid Laurier University (Waterloo, Ontario, Canada) on July 23–24, 2016. This workshop and the resulting book celebrate the 70th birthday of Sergei Abramov (Dorodnicyn Computing Centre of the Russian Academy of Sciences, Moscow), whose highly regarded and inspirational contributions to symbolic methods have become a crucial benchmark of computer algebra and have been broadly adopted by many Computer Algebra systems.
Totally parallel multilevel algorithms
Frederickson, Paul O.
1988-01-01
Four totally parallel algorithms for the solution of a sparse linear system have common characteristics which become quite apparent when they are implemented on a highly parallel hypercube such as the CM2. These four algorithms are Parallel Superconvergent Multigrid (PSMG) of Frederickson and McBryan, Robust Multigrid (RMG) of Hackbusch, the FFT based Spectral Algorithm, and Parallel Cyclic Reduction. In fact, all four can be formulated as particular cases of the same totally parallel multilevel algorithm, which are referred to as TPMA. In certain cases the spectral radius of TPMA is zero, and it is recognized to be a direct algorithm. In many other cases the spectral radius, although not zero, is small enough that a single iteration per timestep keeps the local error within the required tolerance.
Segmental Refinement: A Multigrid Technique for Data Locality
Adams, Mark F.; Brown, Jed; Knepley, Matt; Samtaney, Ravi
2016-01-01
We investigate a domain decomposed multigrid technique, termed segmental refinement, for solving general nonlinear elliptic boundary value problems. We extend the method first proposed in 1994 by analytically and experimentally investigating its complexity. We confirm that communication of traditional parallel multigrid is eliminated on fine grids, with modest amounts of extra work and storage, while maintaining the asymptotic exactness of full multigrid. We observe an accuracy dependence on the segmental refinement subdomain size, which was not considered in the original analysis. We present a communication complexity analysis that quantifies the communication costs ameliorated by segmental refinement and report performance results with up to 64K cores on a Cray XC30.
Segmental Refinement: A Multigrid Technique for Data Locality
Adams, Mark F.
2016-08-04
We investigate a domain decomposed multigrid technique, termed segmental refinement, for solving general nonlinear elliptic boundary value problems. We extend the method first proposed in 1994 by analytically and experimentally investigating its complexity. We confirm that communication of traditional parallel multigrid is eliminated on fine grids, with modest amounts of extra work and storage, while maintaining the asymptotic exactness of full multigrid. We observe an accuracy dependence on the segmental refinement subdomain size, which was not considered in the original analysis. We present a communication complexity analysis that quantifies the communication costs ameliorated by segmental refinement and report performance results with up to 64K cores on a Cray XC30.
Algebraic entropy for algebraic maps
International Nuclear Information System (INIS)
Hone, A N W; Ragnisco, Orlando; Zullo, Federico
2016-01-01
We propose an extension of the concept of algebraic entropy, as introduced by Bellon and Viallet for rational maps, to algebraic maps (or correspondences) of a certain kind. The corresponding entropy is an index of the complexity of the map. The definition inherits the basic properties from the definition of entropy for rational maps. We give an example with positive entropy, as well as two examples taken from the theory of Bäcklund transformations. (letter)
Computations in finite-dimensional Lie algebras
Directory of Open Access Journals (Sweden)
A. M. Cohen
1997-12-01
Full Text Available This paper describes progress made in context with the construction of a general library of Lie algebra algorithms, called ELIAS (Eindhoven Lie Algebra System, within the computer algebra package GAP. A first sketch of the package can be found in Cohen and de Graaf[1]. Since then, in a collaborative effort with G. Ivanyos, the authors have continued to develop algorithms which were implemented in ELIAS by the second author. These activities are part of a bigger project, called ACELA and financed by STW, the Dutch Technology Foundation, which aims at an interactive book on Lie algebras (cf. Cohen and Meertens [2]. This paper gives a global description of the main ways in which to present Lie algebras on a computer. We focus on the transition from a Lie algebra abstractly given by an array of structure constants to a Lie algebra presented as a subalgebra of the Lie algebra of n×n matrices. We describe an algorithm typical of the structure analysis of a finite-dimensional Lie algebra: finding a Levi subalgebra of a Lie algebra.
Segmental Refinement: A Multigrid Technique for Data Locality
Energy Technology Data Exchange (ETDEWEB)
Adams, Mark [Columbia Univ., New York, NY (United States). Applied Physics and Applied Mathematics Dept.; Lawrence Berkeley National Lab. (LBNL), Berkeley, CA (United States)
2014-10-27
We investigate a technique - segmental refinement (SR) - proposed by Brandt in the 1970s as a low memory multigrid method. The technique is attractive for modern computer architectures because it provides high data locality, minimizes network communication, is amenable to loop fusion, and is naturally highly parallel and asynchronous. The network communication minimization property was recognized by Brandt and Diskin in 1994; we continue this work by developing a segmental refinement method for a finite volume discretization of the 3D Laplacian on massively parallel computers. An understanding of the asymptotic complexities, required to maintain textbook multigrid efficiency, are explored experimentally with a simple SR method. A two-level memory model is developed to compare the asymptotic communication complexity of a proposed SR method with traditional parallel multigrid. Performance and scalability are evaluated with a Cray XC30 with up to 64K cores. We achieve modest improvement in scalability from traditional parallel multigrid with a simple SR implementation.
International Nuclear Information System (INIS)
MacCallum, M.A.H.
1990-01-01
The implementation of a new computer algebra system is time consuming: designers of general purpose algebra systems usually say it takes about 50 man-years to create a mature and fully functional system. Hence the range of available systems and their capabilities changes little between one general relativity meeting and the next, despite which there have been significant changes in the period since the last report. The introductory remarks aim to give a brief survey of capabilities of the principal available systems and highlight one or two trends. The reference to the most recent full survey of computer algebra in relativity and brief descriptions of the Maple, REDUCE and SHEEP and other applications are given. (author)
Liesen, Jörg
2015-01-01
This self-contained textbook takes a matrix-oriented approach to linear algebra and presents a complete theory, including all details and proofs, culminating in the Jordan canonical form and its proof. Throughout the development, the applicability of the results is highlighted. Additionally, the book presents special topics from applied linear algebra including matrix functions, the singular value decomposition, the Kronecker product and linear matrix equations. The matrix-oriented approach to linear algebra leads to a better intuition and a deeper understanding of the abstract concepts, and therefore simplifies their use in real world applications. Some of these applications are presented in detailed examples. In several ‘MATLAB-Minutes’ students can comprehend the concepts and results using computational experiments. Necessary basics for the use of MATLAB are presented in a short introduction. Students can also actively work with the material and practice their mathematical skills in more than 300 exerc...
Multigrid methods for S/sub N/ problems
International Nuclear Information System (INIS)
Nowak, P.F.; Larsen, E.W.; Martin, W.R.
1987-01-01
It has long been known that the standard source iteration (SI) method for obtaining iterative solutions of S/sub N/ problems is very slowly converging in optically thick regions with low absorption. The rebalance and diffusion synthetic acceleration (DSA) methods are generalizations of SI that have been developed to accelerate convergence, but neither of these methods has been completely successful. In particular, the rebalance method tends to become unstable in problems where it is needed most (problems with high scattering ratios c = 1), while the DSA method, to be implemented in a stable fashion, requires the solution of a particular system of acceleration equations, and this has been done efficiently in two-dimensional geometries only for the diamond difference S/sub N/ equations. This paper discusses another extension of the SI method, namely, SI combined with the spatial multigrid algorithm (SIMG). This appears to be a viable way to accelerate many S/sub N/ problems in multidimensional geometries, provided the finest mesh consists of cells that are not optically thick
Neural multigrid for gauge theories and other disordered systems
International Nuclear Information System (INIS)
Baeker, M.; Kalkreuter, T.; Mack, G.; Speh, M.
1992-09-01
We present evidence that multigrid works for wave equations in disordered systems, e.g. in the presence of gauge fields, no matter how strong the disorder, but one needs to introduce a 'neural computations' point of view into large scale simulations: First, the system must learn how to do the simulations efficiently, then do the simulation (fast). The method can also be used to provide smooth interpolation kernels which are needed in multigrid Monte Carlo updates. (orig.)
Matrix-dependent multigrid-homogenization for diffusion problems
Energy Technology Data Exchange (ETDEWEB)
Knapek, S. [Institut fuer Informatik tu Muenchen (Germany)
1996-12-31
We present a method to approximately determine the effective diffusion coefficient on the coarse scale level of problems with strongly varying or discontinuous diffusion coefficients. It is based on techniques used also in multigrid, like Dendy`s matrix-dependent prolongations and the construction of coarse grid operators by means of the Galerkin approximation. In numerical experiments, we compare our multigrid-homogenization method with homogenization, renormalization and averaging approaches.
Stoll, R R
1968-01-01
Linear Algebra is intended to be used as a text for a one-semester course in linear algebra at the undergraduate level. The treatment of the subject will be both useful to students of mathematics and those interested primarily in applications of the theory. The major prerequisite for mastering the material is the readiness of the student to reason abstractly. Specifically, this calls for an understanding of the fact that axioms are assumptions and that theorems are logical consequences of one or more axioms. Familiarity with calculus and linear differential equations is required for understand
Jacobson, Nathan
1979-01-01
Lie group theory, developed by M. Sophus Lie in the 19th century, ranks among the more important developments in modern mathematics. Lie algebras comprise a significant part of Lie group theory and are being actively studied today. This book, by Professor Nathan Jacobson of Yale, is the definitive treatment of the subject and can be used as a textbook for graduate courses.Chapter I introduces basic concepts that are necessary for an understanding of structure theory, while the following three chapters present the theory itself: solvable and nilpotent Lie algebras, Carlan's criterion and its
Jacobson, Nathan
2009-01-01
A classic text and standard reference for a generation, this volume and its companion are the work of an expert algebraist who taught at Yale for two decades. Nathan Jacobson's books possess a conceptual and theoretical orientation, and in addition to their value as classroom texts, they serve as valuable references.Volume I explores all of the topics typically covered in undergraduate courses, including the rudiments of set theory, group theory, rings, modules, Galois theory, polynomials, linear algebra, and associative algebra. Its comprehensive treatment extends to such rigorous topics as L
A Critical Study of Agglomerated Multigrid Methods for Diffusion
Nishikawa, Hiroaki; Diskin, Boris; Thomas, James L.
2011-01-01
Agglomerated multigrid techniques used in unstructured-grid methods are studied critically for a model problem representative of laminar diffusion in the incompressible limit. The studied target-grid discretizations and discretizations used on agglomerated grids are typical of current node-centered formulations. Agglomerated multigrid convergence rates are presented using a range of two- and three-dimensional randomly perturbed unstructured grids for simple geometries with isotropic and stretched grids. Two agglomeration techniques are used within an overall topology-preserving agglomeration framework. The results show that multigrid with an inconsistent coarse-grid scheme using only the edge terms (also referred to in the literature as a thin-layer formulation) provides considerable speedup over single-grid methods but its convergence deteriorates on finer grids. Multigrid with a Galerkin coarse-grid discretization using piecewise-constant prolongation and a heuristic correction factor is slower and also grid-dependent. In contrast, grid-independent convergence rates are demonstrated for multigrid with consistent coarse-grid discretizations. Convergence rates of multigrid cycles are verified with quantitative analysis methods in which parts of the two-grid cycle are replaced by their idealized counterparts.
Indian Academy of Sciences (India)
polynomial) division have been found in Vedic Mathematics which are dated much before Euclid's algorithm. A programming language Is used to describe an algorithm for execution on a computer. An algorithm expressed using a programming.
Tracing a planar algebraic curve
International Nuclear Information System (INIS)
Chen Falai; Kozak, J.
1994-09-01
In this paper, an algorithm that determines a real algebraic curve is outlined. Its basic step is to divide the plane into subdomains that include only simple branches of the algebraic curve without singular points. Each of the branches is then stably and efficiently traced in the particular subdomain. Except for the tracing, the algorithm requires only a couple of simple operations on polynomials that can be carried out exactly if the coefficients are rational, and the determination of zeros of several polynomials of one variable. (author). 5 refs, 4 figs
Indian Academy of Sciences (India)
tion - 6. How Architectural Features Affect. Building During Earthquakes? C VRMurty. 48 Turbulence and Dispersion. K 5 Gandhi. BOOK REVIEWS. 86 Algebraic Topology. Siddhartha Gadgil. Front Cover. - .. ..-.......... -. Back Cover. Two-dimensional vertical section through a turbulent plume. (Courtesy: G S Shat, CAOS, IISc.).
Indian Academy of Sciences (India)
Deligne, Mumford and Artin [DM, Ar2]) and consider algebraic stacks, then we can cons- truct the 'moduli ... the moduli scheme and the moduli stack of vector bundles. First I will give ... 1–31. © Printed in India. 1 ...... Cultura, Spain. References.
Computational linear and commutative algebra
Kreuzer, Martin
2016-01-01
This book combines, in a novel and general way, an extensive development of the theory of families of commuting matrices with applications to zero-dimensional commutative rings, primary decompositions and polynomial system solving. It integrates the Linear Algebra of the Third Millennium, developed exclusively here, with classical algorithmic and algebraic techniques. Even the experienced reader will be pleasantly surprised to discover new and unexpected aspects in a variety of subjects including eigenvalues and eigenspaces of linear maps, joint eigenspaces of commuting families of endomorphisms, multiplication maps of zero-dimensional affine algebras, computation of primary decompositions and maximal ideals, and solution of polynomial systems. This book completes a trilogy initiated by the uncharacteristically witty books Computational Commutative Algebra 1 and 2 by the same authors. The material treated here is not available in book form, and much of it is not available at all. The authors continue to prese...
A faithful functor among algebras and graphs
Falcón Ganfornina, Óscar Jesús; Falcón Ganfornina, Raúl Manuel; Núñez Valdés, Juan; Pacheco Martínez, Ana María; Villar Liñán, María Trinidad; Vigo Aguiar, Jesús (Coordinador)
2016-01-01
The problem of identifying a functor between the categories of algebras and graphs is currently open. Based on a known algorithm that identifies isomorphisms of Latin squares with isomorphism of vertex-colored graphs, we describe here a pair of graphs that enable us to find a faithful functor between finite-dimensional algebras over finite fields and these graphs.
An algebraic approach to the scattering equations
Energy Technology Data Exchange (ETDEWEB)
Huang, Rijun; Rao, Junjie [Zhejiang Institute of Modern Physics, Zhejiang University,Hangzhou, 310027 (China); Feng, Bo [Zhejiang Institute of Modern Physics, Zhejiang University,Hangzhou, 310027 (China); Center of Mathematical Science, Zhejiang University,Hangzhou, 310027 (China); He, Yang-Hui [School of Physics, NanKai University,Tianjin, 300071 (China); Department of Mathematics, City University,London, EC1V 0HB (United Kingdom); Merton College, University of Oxford,Oxford, OX14JD (United Kingdom)
2015-12-10
We employ the so-called companion matrix method from computational algebraic geometry, tailored for zero-dimensional ideals, to study the scattering equations. The method renders the CHY-integrand of scattering amplitudes computable using simple linear algebra and is amenable to an algorithmic approach. Certain identities in the amplitudes as well as rationality of the final integrand become immediate in this formalism.
An algebraic approach to the scattering equations
International Nuclear Information System (INIS)
Huang, Rijun; Rao, Junjie; Feng, Bo; He, Yang-Hui
2015-01-01
We employ the so-called companion matrix method from computational algebraic geometry, tailored for zero-dimensional ideals, to study the scattering equations. The method renders the CHY-integrand of scattering amplitudes computable using simple linear algebra and is amenable to an algorithmic approach. Certain identities in the amplitudes as well as rationality of the final integrand become immediate in this formalism.
Algebraic characterizations of measure algebras
Czech Academy of Sciences Publication Activity Database
Jech, Thomas
2008-01-01
Roč. 136, č. 4 (2008), s. 1285-1294 ISSN 0002-9939 R&D Projects: GA AV ČR IAA100190509 Institutional research plan: CEZ:AV0Z10190503 Keywords : Von - Neumann * sequential topology * Boolean-algebras * Souslins problem * Submeasures Subject RIV: BA - General Mathematics Impact factor: 0.584, year: 2008
Quantum W-algebras and elliptic algebras
International Nuclear Information System (INIS)
Feigin, B.; Kyoto Univ.; Frenkel, E.
1996-01-01
We define a quantum W-algebra associated to sl N as an associative algebra depending on two parameters. For special values of the parameters, this algebra becomes the ordinary W-algebra of sl N , or the q-deformed classical W-algebra of sl N . We construct free field realizations of the quantum W-algebras and the screening currents. We also point out some interesting elliptic structures arising in these algebras. In particular, we show that the screening currents satisfy elliptic analogues of the Drinfeld relations in U q (n). (orig.)
International Nuclear Information System (INIS)
Mohammad, N.; Siddiqui, A.H.
1987-11-01
The notion of a 2-Banach algebra is introduced and its structure is studied. After a short discussion of some fundamental properties of bivectors and tensor product, several classical results of Banach algebras are extended to the 2-Banach algebra case. A condition under which a 2-Banach algebra becomes a Banach algebra is obtained and the relation between algebra of bivectors and 2-normed algebra is discussed. 11 refs
Computers in nonassociative rings and algebras
Beck, Robert E
1977-01-01
Computers in Nonassociative Rings and Algebras provides information pertinent to the computational aspects of nonassociative rings and algebras. This book describes the algorithmic approaches for solving problems using a computer.Organized into 10 chapters, this book begins with an overview of the concept of a symmetrized power of a group representation. This text then presents data structures and other computational methods that may be useful in the field of computational algebra. Other chapters consider several mathematical ideas, including identity processing in nonassociative algebras, str
Mulligan, Jeffrey B.
2017-01-01
A color algebra refers to a system for computing sums and products of colors, analogous to additive and subtractive color mixtures. The difficulty addressed here is the fact that, because of metamerism, we cannot know with certainty the spectrum that produced a particular color solely on the basis of sensory data. Knowledge of the spectrum is not required to compute additive mixture of colors, but is critical for subtractive (multiplicative) mixture. Therefore, we cannot predict with certainty the multiplicative interactions between colors based solely on sensory data. There are two potential applications of a color algebra: first, to aid modeling phenomena of human visual perception, such as color constancy and transparency; and, second, to provide better models of the interactions of lights and surfaces for computer graphics rendering.
International Nuclear Information System (INIS)
Jacob, M.
1967-01-01
The first three chapters of these lecture notes are devoted to generalities concerning current algebra. The weak currents are defined, and their main properties given (V-A hypothesis, conserved vector current, selection rules, partially conserved axial current,...). The SU (3) x SU (3) algebra of Gell-Mann is introduced, and the general properties of the non-leptonic weak Hamiltonian are discussed. Chapters 4 to 9 are devoted to some important applications of the algebra. First one proves the Adler- Weisberger formula, in two different ways, by either the infinite momentum frame, or the near-by singularities method. In the others chapters, the latter method is the only one used. The following topics are successively dealt with: semi leptonic decays of K mesons and hyperons, Kroll- Ruderman theorem, non leptonic decays of K mesons and hyperons ( ΔI = 1/2 rule), low energy theorems concerning processes with emission (or absorption) of a pion or a photon, super-convergence sum rules, and finally, neutrino reactions. (author) [fr
Algebraic classification of the conformal tensor
International Nuclear Information System (INIS)
Ares de Parga, Gonzalo; Chavoya, O.; Lopez B, J.L.; Ovando Z, Gerardo
1989-01-01
Starting from the Petrov matrix method, we deduce a new algorithm (adaptable to computers), within the Newman-Penrose formalism, to obtain the algebraic type of the Weyl tensor in general relativity. (author)
International Nuclear Information System (INIS)
Baker, K.L.
2005-01-01
This article details a multigrid algorithm that is suitable for least-squares wave-front reconstruction of Shack-Hartmann and shearing interferometer wave-front sensors. The algorithm detailed in this article is shown to scale with the number of subapertures in the same fashion as fast Fourier transform techniques, making it suitable for use in applications requiring a large number of subapertures and high Strehl ratio systems such as for high spatial frequency characterization of high-density plasmas, optics metrology, and multiconjugate and extreme adaptive optics systems
Kleyn, Aleks
2007-01-01
The concept of F-algebra and its representation can be extended to an arbitrary bundle. We define operations of fibered F-algebra in fiber. The paper presents the representation theory of of fibered F-algebra as well as a comparison of representation of F-algebra and of representation of fibered F-algebra.
Indian Academy of Sciences (India)
to as 'divide-and-conquer'. Although there has been a large effort in realizing efficient algorithms, there are not many universally accepted algorithm design paradigms. In this article, we illustrate algorithm design techniques such as balancing, greedy strategy, dynamic programming strategy, and backtracking or traversal of ...
Corrochano, Eduardo Bayro
2010-01-01
This book presents contributions from a global selection of experts in the field. This useful text offers new insights and solutions for the development of theorems, algorithms and advanced methods for real-time applications across a range of disciplines. Written in an accessible style, the discussion of all applications is enhanced by the inclusion of numerous examples, figures and experimental analysis. Features: provides a thorough discussion of several tasks for image processing, pattern recognition, computer vision, robotics and computer graphics using the geometric algebra framework; int
Lopez, Cesar
2014-01-01
MATLAB is a high-level language and environment for numerical computation, visualization, and programming. Using MATLAB, you can analyze data, develop algorithms, and create models and applications. The language, tools, and built-in math functions enable you to explore multiple approaches and reach a solution faster than with spreadsheets or traditional programming languages, such as C/C++ or Java. MATLAB Linear Algebra introduces you to the MATLAB language with practical hands-on instructions and results, allowing you to quickly achieve your goals. In addition to giving an introduction to
Cleaveland, Rance; Luettgen, Gerald; Natarajan, V.
1999-01-01
This paper surveys the semantic ramifications of extending traditional process algebras with notions of priority that allow for some transitions to be given precedence over others. These enriched formalisms allow one to model system features such as interrupts, prioritized choice, or real-time behavior. Approaches to priority in process algebras can be classified according to whether the induced notion of preemption on transitions is global or local and whether priorities are static or dynamic. Early work in the area concentrated on global pre-emption and static priorities and led to formalisms for modeling interrupts and aspects of real-time, such as maximal progress, in centralized computing environments. More recent research has investigated localized notions of pre-emption in which the distribution of systems is taken into account, as well as dynamic priority approaches, i.e., those where priority values may change as systems evolve. The latter allows one to model behavioral phenomena such as scheduling algorithms and also enables the efficient encoding of real-time semantics. Technically, this paper studies the different models of priorities by presenting extensions of Milner's Calculus of Communicating Systems (CCS) with static and dynamic priority as well as with notions of global and local pre- emption. In each case the operational semantics of CCS is modified appropriately, behavioral theories based on strong and weak bisimulation are given, and related approaches for different process-algebraic settings are discussed.
Energy Technology Data Exchange (ETDEWEB)
White, M.J.; Iskander, M.F. [Univ. of Utah, Salt Lake City, UT (United States). Electrical Engineering Dept.; Kimrey, H.D. [Oak Ridge National Lab., TN (United States)
1996-12-31
The Finite-Difference Time-Domain (FDTD) code available at the University of Utah has been used to simulate sintering of ceramics in single and multimode cavities, and many useful results have been reported in literature. More detailed and accurate results, specifically around and including the ceramic sample, are often desired to help evaluate the adequacy of the heating procedure. In electrically large multimode cavities, however, computer memory requirements limit the number of the mathematical cells, and the desired resolution is impractical to achieve due to limited computer resources. Therefore, an FDTD algorithm which incorporates multiple-grid regions with variable-grid sizes is required to adequately perform the desired simulations. In this paper the authors describe the development of a three-dimensional multi-grid FDTD code to help focus a large number of cells around the desired region. Test geometries were solved using a uniform-grid and the developed multi-grid code to help validate the results from the developed code. Results from these comparisons, as well as the results of comparisons between the developed FDTD code and other available variable-grid codes are presented. In addition, results from the simulation of realistic microwave sintering experiments showed improved resolution in critical sites inside the three-dimensional sintering cavity. With the validation of the FDTD code, simulations were performed for electrically large, multimode, microwave sintering cavities to fully demonstrate the advantages of the developed multi-grid FDTD code.
Accelerating Lattice QCD Multigrid on GPUs Using Fine-Grained Parallelization
Energy Technology Data Exchange (ETDEWEB)
Clark, M. A. [NVIDIA Corp., Santa Clara; Joó, Bálint [Jefferson Lab; Strelchenko, Alexei [Fermilab; Cheng, Michael [Boston U., Ctr. Comp. Sci.; Gambhir, Arjun [William-Mary Coll.; Brower, Richard [Boston U.
2016-12-22
The past decade has witnessed a dramatic acceleration of lattice quantum chromodynamics calculations in nuclear and particle physics. This has been due to both significant progress in accelerating the iterative linear solvers using multi-grid algorithms, and due to the throughput improvements brought by GPUs. Deploying hierarchical algorithms optimally on GPUs is non-trivial owing to the lack of parallelism on the coarse grids, and as such, these advances have not proved multiplicative. Using the QUDA library, we demonstrate that by exposing all sources of parallelism that the underlying stencil problem possesses, and through appropriate mapping of this parallelism to the GPU architecture, we can achieve high efficiency even for the coarsest of grids. Results are presented for the Wilson-Clover discretization, where we demonstrate up to 10x speedup over present state-of-the-art GPU-accelerated methods on Titan. Finally, we look to the future, and consider the software implications of our findings.
Investigations on application of multigrid method to MHD equilibrium analysis
International Nuclear Information System (INIS)
Ikuno, Soichiro
2000-01-01
The potentiality of application for Multi-grid method to MHD equilibrium analysis is investigated. The nonlinear eigenvalue problem often appears when the MHD equilibria are determined by solving the Grad-Shafranov equation numerically. After linearization of the equation, the problem is solved by use of the iterative method. Although the Red-Black SOR method or Gauss-Seidel method is often used for the solution of the linearized equation, it takes much CPU time to solve the problem. The Multi-grid method is compared with the SOR method for the Poisson Problem. The results of computations show that the CPU time required for the Multi-grid method is about 1000 times as small as that for the SOR method. (author)
A multigrid solution method for mixed hybrid finite elements
Energy Technology Data Exchange (ETDEWEB)
Schmid, W. [Universitaet Augsburg (Germany)
1996-12-31
We consider the multigrid solution of linear equations arising within the discretization of elliptic second order boundary value problems of the form by mixed hybrid finite elements. Using the equivalence of mixed hybrid finite elements and non-conforming nodal finite elements, we construct a multigrid scheme for the corresponding non-conforming finite elements, and, by this equivalence, for the mixed hybrid finite elements, following guidelines from Arbogast/Chen. For a rectangular triangulation of the computational domain, this non-conforming schemes are the so-called nodal finite elements. We explicitly construct prolongation and restriction operators for this type of non-conforming finite elements. We discuss the use of plain multigrid and the multilevel-preconditioned cg-method and compare their efficiency in numerical tests.
International Nuclear Information System (INIS)
Dragon, N.
1979-01-01
The possible use of trilinear algebras as symmetry algebras for para-Fermi fields is investigated. The shortcomings of the examples are argued to be a general feature of such generalized algebras. (author)
International Nuclear Information System (INIS)
Yau, Donald
2011-01-01
We study a twisted generalization of Novikov algebras, called Hom-Novikov algebras, in which the two defining identities are twisted by a linear map. It is shown that Hom-Novikov algebras can be obtained from Novikov algebras by twisting along any algebra endomorphism. All algebra endomorphisms on complex Novikov algebras of dimensions 2 or 3 are computed, and their associated Hom-Novikov algebras are described explicitly. Another class of Hom-Novikov algebras is constructed from Hom-commutative algebras together with a derivation, generalizing a construction due to Dorfman and Gel'fand. Two other classes of Hom-Novikov algebras are constructed from Hom-Lie algebras together with a suitable linear endomorphism, generalizing a construction due to Bai and Meng.
International Nuclear Information System (INIS)
Vadlamani, Srinath; Kruger, Scott; Austin, Travis
2008-01-01
Extended magnetohydrodynamic (MHD) codes are used to model the large, slow-growing instabilities that are projected to limit the performance of International Thermonuclear Experimental Reactor (ITER). The multiscale nature of the extended MHD equations requires an implicit approach. The current linear solvers needed for the implicit algorithm scale poorly because the resultant matrices are so ill-conditioned. A new solver is needed, especially one that scales to the petascale. The most successful scalable parallel processor solvers to date are multigrid solvers. Applying multigrid techniques to a set of equations whose fundamental modes are dispersive waves is a promising solution to CEMM problems. For the Phase 1, we implemented multigrid preconditioners from the HYPRE project of the Center for Applied Scientific Computing at LLNL via PETSc of the DOE SciDAC TOPS for the real matrix systems of the extended MHD code NIMROD which is a one of the primary modeling codes of the OFES-funded Center for Extended Magnetohydrodynamic Modeling (CEMM) SciDAC. We implemented the multigrid solvers on the fusion test problem that allows for real matrix systems with success, and in the process learned about the details of NIMROD data structures and the difficulties of inverting NIMROD operators. The further success of this project will allow for efficient usage of future petascale computers at the National Leadership Facilities: Oak Ridge National Laboratory, Argonne National Laboratory, and National Energy Research Scientific Computing Center. The project will be a collaborative effort between computational plasma physicists and applied mathematicians at Tech-X Corporation, applied mathematicians Front Range Scientific Computations, Inc. (who are collaborators on the HYPRE project), and other computational plasma physicists involved with the CEMM project.
Bliss, Gilbert Ames
1933-01-01
This book, immediately striking for its conciseness, is one of the most remarkable works ever produced on the subject of algebraic functions and their integrals. The distinguishing feature of the book is its third chapter, on rational functions, which gives an extremely brief and clear account of the theory of divisors.... A very readable account is given of the topology of Riemann surfaces and of the general properties of abelian integrals. Abel's theorem is presented, with some simple applications. The inversion problem is studied for the cases of genus zero and genus unity. The chapter on t
Esmaily, M.; Jofre, L.; Mani, A.; Iaccarino, G.
2018-03-01
A geometric multigrid algorithm is introduced for solving nonsymmetric linear systems resulting from the discretization of the variable density Navier-Stokes equations on nonuniform structured rectilinear grids and high-Reynolds number flows. The restriction operation is defined such that the resulting system on the coarser grids is symmetric, thereby allowing for the use of efficient smoother algorithms. To achieve an optimal rate of convergence, the sequence of interpolation and restriction operations are determined through a dynamic procedure. A parallel partitioning strategy is introduced to minimize communication while maintaining the load balance between all processors. To test the proposed algorithm, we consider two cases: 1) homogeneous isotropic turbulence discretized on uniform grids and 2) turbulent duct flow discretized on stretched grids. Testing the algorithm on systems with up to a billion unknowns shows that the cost varies linearly with the number of unknowns. This O (N) behavior confirms the robustness of the proposed multigrid method regarding ill-conditioning of large systems characteristic of multiscale high-Reynolds number turbulent flows. The robustness of our method to density variations is established by considering cases where density varies sharply in space by a factor of up to 104, showing its applicability to two-phase flow problems. Strong and weak scalability studies are carried out, employing up to 30,000 processors, to examine the parallel performance of our implementation. Excellent scalability of our solver is shown for a granularity as low as 104 to 105 unknowns per processor. At its tested peak throughput, it solves approximately 4 billion unknowns per second employing over 16,000 processors with a parallel efficiency higher than 50%.
Scalable smoothing strategies for a geometric multigrid method for the immersed boundary equations
Energy Technology Data Exchange (ETDEWEB)
Bhalla, Amneet Pal Singh [Univ. of North Carolina, Chapel Hill, NC (United States); Knepley, Matthew G. [Rice Univ., Houston, TX (United States); Adams, Mark F. [Lawrence Berkeley National Lab. (LBNL), Berkeley, CA (United States); Guy, Robert D. [Univ. of California, Davis, CA (United States); Griffith, Boyce E. [Univ. of North Carolina, Chapel Hill, NC (United States)
2016-12-20
The immersed boundary (IB) method is a widely used approach to simulating fluid-structure interaction (FSI). Although explicit versions of the IB method can suffer from severe time step size restrictions, these methods remain popular because of their simplicity and generality. In prior work (Guy et al., Adv Comput Math, 2015), some of us developed a geometric multigrid preconditioner for a stable semi-implicit IB method under Stokes flow conditions; however, this solver methodology used a Vanka-type smoother that presented limited opportunities for parallelization. This work extends this Stokes-IB solver methodology by developing smoothing techniques that are suitable for parallel implementation. Specifically, we demonstrate that an additive version of the Vanka smoother can yield an effective multigrid preconditioner for the Stokes-IB equations, and we introduce an efficient Schur complement-based smoother that is also shown to be effective for the Stokes-IB equations. We investigate the performance of these solvers for a broad range of material stiffnesses, both for Stokes flows and flows at nonzero Reynolds numbers, and for thick and thin structural models. We show here that linear solver performance degrades with increasing Reynolds number and material stiffness, especially for thin interface cases. Nonetheless, the proposed approaches promise to yield effective solution algorithms, especially at lower Reynolds numbers and at modest-to-high elastic stiffnesses.
Iterated Leavitt Path Algebras
International Nuclear Information System (INIS)
Hazrat, R.
2009-11-01
Leavitt path algebras associate to directed graphs a Z-graded algebra and in their simplest form recover the Leavitt algebras L(1,k). In this note, we introduce iterated Leavitt path algebras associated to directed weighted graphs which have natural ± Z grading and in their simplest form recover the Leavitt algebras L(n,k). We also characterize Leavitt path algebras which are strongly graded. (author)
Grätzer, George
1979-01-01
Universal Algebra, heralded as ". . . the standard reference in a field notorious for the lack of standardization . . .," has become the most authoritative, consistently relied on text in a field with applications in other branches of algebra and other fields such as combinatorics, geometry, and computer science. Each chapter is followed by an extensive list of exercises and problems. The "state of the art" account also includes new appendices (with contributions from B. Jónsson, R. Quackenbush, W. Taylor, and G. Wenzel) and a well-selected additional bibliography of over 1250 papers and books which makes this a fine work for students, instructors, and researchers in the field. "This book will certainly be, in the years to come, the basic reference to the subject." --- The American Mathematical Monthly (First Edition) "In this reviewer's opinion [the author] has more than succeeded in his aim. The problems at the end of each chapter are well-chosen; there are more than 650 of them. The book is especially sui...
Yoneda algebras of almost Koszul algebras
Indian Academy of Sciences (India)
Abstract. Let k be an algebraically closed field, A a finite dimensional connected. (p,q)-Koszul self-injective algebra with p, q ≥ 2. In this paper, we prove that the. Yoneda algebra of A is isomorphic to a twisted polynomial algebra A![t; β] in one inde- terminate t of degree q +1 in which A! is the quadratic dual of A, β is an ...
Miyanishi, Masayoshi
2000-01-01
Open algebraic surfaces are a synonym for algebraic surfaces that are not necessarily complete. An open algebraic surface is understood as a Zariski open set of a projective algebraic surface. There is a long history of research on projective algebraic surfaces, and there exists a beautiful Enriques-Kodaira classification of such surfaces. The research accumulated by Ramanujan, Abhyankar, Moh, and Nagata and others has established a classification theory of open algebraic surfaces comparable to the Enriques-Kodaira theory. This research provides powerful methods to study the geometry and topology of open algebraic surfaces. The theory of open algebraic surfaces is applicable not only to algebraic geometry, but also to other fields, such as commutative algebra, invariant theory, and singularities. This book contains a comprehensive account of the theory of open algebraic surfaces, as well as several applications, in particular to the study of affine surfaces. Prerequisite to understanding the text is a basic b...
Said-Houari, Belkacem
2017-01-01
This self-contained, clearly written textbook on linear algebra is easily accessible for students. It begins with the simple linear equation and generalizes several notions from this equation for the system of linear equations and introduces the main ideas using matrices. It then offers a detailed chapter on determinants and introduces the main ideas with detailed proofs. The third chapter introduces the Euclidean spaces using very simple geometric ideas and discusses various major inequalities and identities. These ideas offer a solid basis for understanding general Hilbert spaces in functional analysis. The following two chapters address general vector spaces, including some rigorous proofs to all the main results, and linear transformation: areas that are ignored or are poorly explained in many textbooks. Chapter 6 introduces the idea of matrices using linear transformation, which is easier to understand than the usual theory of matrices approach. The final two chapters are more advanced, introducing t...
Primal-Dual Interior Point Multigrid Method for Topology Optimization
Czech Academy of Sciences Publication Activity Database
Kočvara, Michal; Mohammed, S.
2016-01-01
Roč. 38, č. 5 (2016), B685-B709 ISSN 1064-8275 Grant - others:European Commission - EC(XE) 313781 Institutional support: RVO:67985556 Keywords : topology optimization * multigrid method s * interior point method Subject RIV: BA - General Mathematics Impact factor: 2.195, year: 2016 http://library.utia.cas.cz/separaty/2016/MTR/kocvara-0462418.pdf
On multigrid-CG for efficient topology optimization
DEFF Research Database (Denmark)
Amir, Oded; Aage, Niels; Lazarov, Boyan Stefanov
2014-01-01
reduction is obtained by exploiting specific characteristics of a multigrid preconditioned conjugate gradients (MGCG) solver. In particular, the number of MGCG iterations is reduced by relating it to the geometric parameters of the problem. At the same time, accurate outcome of the optimization process...
The Yoneda algebra of a K2 algebra need not be another K2 algebra
Cassidy, T.; Phan, C.; Shelton, B.
2010-01-01
The Yoneda algebra of a Koszul algebra or a D-Koszul algebra is Koszul. K2 algebras are a natural generalization of Koszul algebras, and one would hope that the Yoneda algebra of a K2 algebra would be another K2 algebra. We show that this is not necessarily the case by constructing a monomial K2 algebra for which the corresponding Yoneda algebra is not K2.
Indian Academy of Sciences (India)
ticians but also forms the foundation of computer science. Two ... with methods of developing algorithms for solving a variety of problems but ... applications of computers in science and engineer- ... numerical calculus are as important. We will ...
Dzhumadil'daev, A. S.
2002-01-01
Algebras with identity $(a\\star b)\\star (c\\star d) -(a\\star d)\\star(c\\star b)$ $=(a,b,c)\\star d-(a,d,c)\\star b$ are studied. Novikov algebras under Jordan multiplication and Leibniz dual algebras satisfy this identity. If algebra with such identity has unit, then it is associative and commutative.
Joux, Antoine
2009-01-01
Illustrating the power of algorithms, Algorithmic Cryptanalysis describes algorithmic methods with cryptographically relevant examples. Focusing on both private- and public-key cryptographic algorithms, it presents each algorithm either as a textual description, in pseudo-code, or in a C code program.Divided into three parts, the book begins with a short introduction to cryptography and a background chapter on elementary number theory and algebra. It then moves on to algorithms, with each chapter in this section dedicated to a single topic and often illustrated with simple cryptographic applic
Introduction to relation algebras relation algebras
Givant, Steven
2017-01-01
The first volume of a pair that charts relation algebras from novice to expert level, this text offers a comprehensive grounding for readers new to the topic. Upon completing this introduction, mathematics students may delve into areas of active research by progressing to the second volume, Advanced Topics in Relation Algebras; computer scientists, philosophers, and beyond will be equipped to apply these tools in their own field. The careful presentation establishes first the arithmetic of relation algebras, providing ample motivation and examples, then proceeds primarily on the basis of algebraic constructions: subalgebras, homomorphisms, quotient algebras, and direct products. Each chapter ends with a historical section and a substantial number of exercises. The only formal prerequisite is a background in abstract algebra and some mathematical maturity, though the reader will also benefit from familiarity with Boolean algebra and naïve set theory. The measured pace and outstanding clarity are particularly ...
International Nuclear Information System (INIS)
Ludu, A.; Greiner, M.
1995-09-01
A non-linear associative algebra is realized in terms of translation and dilation operators, and a wavelet structure generating algebra is obtained. We show that this algebra is a q-deformation of the Fourier series generating algebra, and reduces to this for certain value of the deformation parameter. This algebra is also homeomorphic with the q-deformed su q (2) algebra and some of its extensions. Through this algebraic approach new methods for obtaining the wavelets are introduced. (author). 20 refs
Foulis, David J.; Pulmannov, Sylvia
2018-04-01
Using a representation theorem of Erik Alfsen, Frederic Schultz, and Erling Størmer for special JB-algebras, we prove that a synaptic algebra is norm complete (i.e., Banach) if and only if it is isomorphic to the self-adjoint part of a Rickart C∗-algebra. Also, we give conditions on a Banach synaptic algebra that are equivalent to the condition that it is isomorphic to the self-adjoint part of an AW∗-algebra. Moreover, we study some relationships between synaptic algebras and so-called generalized Hermitian algebras.
Quantum complexity of graph and algebraic problems
International Nuclear Information System (INIS)
Doern, Sebastian
2008-01-01
This thesis is organized as follows: In Chapter 2 we give some basic notations, definitions and facts from linear algebra, graph theory, group theory and quantum computation. In Chapter 3 we describe three important methods for the construction of quantum algorithms. We present the quantum search algorithm by Grover, the quantum amplitude amplification and the quantum walk search technique by Magniez et al. These three tools are the basis for the development of our new quantum algorithms for graph and algebra problems. In Chapter 4 we present two tools for proving quantum query lower bounds. We present the quantum adversary method by Ambainis and the polynomial method introduced by Beals et al. The quantum adversary tool is very useful to prove good lower bounds for many graph and algebra problems. The part of the thesis containing the original results is organized in two parts. In the first part we consider the graph problems. In Chapter 5 we give a short summary of known quantum graph algorithms. In Chapter 6 to 8 we study the complexity of our new algorithms for matching problems, graph traversal and independent set problems on quantum computers. In the second part of our thesis we present new quantum algorithms for algebraic problems. In Chapter 9 to 10 we consider group testing problems and prove quantum complexity bounds for important problems from linear algebra. (orig.)
Quantum complexity of graph and algebraic problems
Energy Technology Data Exchange (ETDEWEB)
Doern, Sebastian
2008-02-04
This thesis is organized as follows: In Chapter 2 we give some basic notations, definitions and facts from linear algebra, graph theory, group theory and quantum computation. In Chapter 3 we describe three important methods for the construction of quantum algorithms. We present the quantum search algorithm by Grover, the quantum amplitude amplification and the quantum walk search technique by Magniez et al. These three tools are the basis for the development of our new quantum algorithms for graph and algebra problems. In Chapter 4 we present two tools for proving quantum query lower bounds. We present the quantum adversary method by Ambainis and the polynomial method introduced by Beals et al. The quantum adversary tool is very useful to prove good lower bounds for many graph and algebra problems. The part of the thesis containing the original results is organized in two parts. In the first part we consider the graph problems. In Chapter 5 we give a short summary of known quantum graph algorithms. In Chapter 6 to 8 we study the complexity of our new algorithms for matching problems, graph traversal and independent set problems on quantum computers. In the second part of our thesis we present new quantum algorithms for algebraic problems. In Chapter 9 to 10 we consider group testing problems and prove quantum complexity bounds for important problems from linear algebra. (orig.)
Rationality problem for algebraic tori
Hoshi, Akinari
2017-01-01
The authors give the complete stably rational classification of algebraic tori of dimensions 4 and 5 over a field k. In particular, the stably rational classification of norm one tori whose Chevalley modules are of rank 4 and 5 is given. The authors show that there exist exactly 487 (resp. 7, resp. 216) stably rational (resp. not stably but retract rational, resp. not retract rational) algebraic tori of dimension 4, and there exist exactly 3051 (resp. 25, resp. 3003) stably rational (resp. not stably but retract rational, resp. not retract rational) algebraic tori of dimension 5. The authors make a procedure to compute a flabby resolution of a G-lattice effectively by using the computer algebra system GAP. Some algorithms may determine whether the flabby class of a G-lattice is invertible (resp. zero) or not. Using the algorithms, the suthors determine all the flabby and coflabby G-lattices of rank up to 6 and verify that they are stably permutation. The authors also show that the Krull-Schmidt theorem for G-...
The finite volume element (FVE) and multigrid method for the incompressible Navier-Stokes equations
International Nuclear Information System (INIS)
Gu Lizhen; Bao Weizhu
1992-01-01
The authors apply FVE method to discrete INS equations with the original variable, in which the bilinear square finite element and the square finite volume are chosen. The discrete schemes of INS equations are presented. The FMV multigrid algorithm is applied to solve that discrete system, where DGS iteration is used as smoother, DGS distributive mode for the INS discrete system is also presented. The sample problems for the square cavity flow with Reynolds number Re≤100 are successfully calculated. The numerical solutions show that the results with 1 FMV is satisfactory and when Re is not large, The FVE discrete scheme of the conservative INS equations and that of non-conservative INS equations with linearization both can provide almost same accuracy
Quantum cluster algebras and quantum nilpotent algebras
Goodearl, Kenneth R.; Yakimov, Milen T.
2014-01-01
A major direction in the theory of cluster algebras is to construct (quantum) cluster algebra structures on the (quantized) coordinate rings of various families of varieties arising in Lie theory. We prove that all algebras in a very large axiomatically defined class of noncommutative algebras possess canonical quantum cluster algebra structures. Furthermore, they coincide with the corresponding upper quantum cluster algebras. We also establish analogs of these results for a large class of Poisson nilpotent algebras. Many important families of coordinate rings are subsumed in the class we are covering, which leads to a broad range of applications of the general results to the above-mentioned types of problems. As a consequence, we prove the Berenstein–Zelevinsky conjecture [Berenstein A, Zelevinsky A (2005) Adv Math 195:405–455] for the quantized coordinate rings of double Bruhat cells and construct quantum cluster algebra structures on all quantum unipotent groups, extending the theorem of Geiß et al. [Geiß C, et al. (2013) Selecta Math 19:337–397] for the case of symmetric Kac–Moody groups. Moreover, we prove that the upper cluster algebras of Berenstein et al. [Berenstein A, et al. (2005) Duke Math J 126:1–52] associated with double Bruhat cells coincide with the corresponding cluster algebras. PMID:24982197
Numerical linear algebra theory and applications
Beilina, Larisa; Karchevskii, Mikhail
2017-01-01
This book combines a solid theoretical background in linear algebra with practical algorithms for numerical solution of linear algebra problems. Developed from a number of courses taught repeatedly by the authors, the material covers topics like matrix algebra, theory for linear systems of equations, spectral theory, vector and matrix norms combined with main direct and iterative numerical methods, least squares problems, and eigen problems. Numerical algorithms illustrated by computer programs written in MATLAB® are also provided as supplementary material on SpringerLink to give the reader a better understanding of professional numerical software for the solution of real-life problems. Perfect for a one- or two-semester course on numerical linear algebra, matrix computation, and large sparse matrices, this text will interest students at the advanced undergraduate or graduate level.
Commutative algebra constructive methods finite projective modules
Lombardi, Henri
2015-01-01
Translated from the popular French edition, this book offers a detailed introduction to various basic concepts, methods, principles, and results of commutative algebra. It takes a constructive viewpoint in commutative algebra and studies algorithmic approaches alongside several abstract classical theories. Indeed, it revisits these traditional topics with a new and simplifying manner, making the subject both accessible and innovative. The algorithmic aspects of such naturally abstract topics as Galois theory, Dedekind rings, Prüfer rings, finitely generated projective modules, dimension theory of commutative rings, and others in the current treatise, are all analysed in the spirit of the great developers of constructive algebra in the nineteenth century. This updated and revised edition contains over 350 well-arranged exercises, together with their helpful hints for solution. A basic knowledge of linear algebra, group theory, elementary number theory as well as the fundamentals of ring and module theory is r...
Classification and identification of Lie algebras
Snobl, Libor
2014-01-01
The purpose of this book is to serve as a tool for researchers and practitioners who apply Lie algebras and Lie groups to solve problems arising in science and engineering. The authors address the problem of expressing a Lie algebra obtained in some arbitrary basis in a more suitable basis in which all essential features of the Lie algebra are directly visible. This includes algorithms accomplishing decomposition into a direct sum, identification of the radical and the Levi decomposition, and the computation of the nilradical and of the Casimir invariants. Examples are given for each algorithm. For low-dimensional Lie algebras this makes it possible to identify the given Lie algebra completely. The authors provide a representative list of all Lie algebras of dimension less or equal to 6 together with their important properties, including their Casimir invariants. The list is ordered in a way to make identification easy, using only basis independent properties of the Lie algebras. They also describe certain cl...
Numerical linear algebra with applications using Matlab
Ford, William
2014-01-01
Designed for those who want to gain a practical knowledge of modern computational techniques for the numerical solution of linear algebra problems, Numerical Linear Algebra with Applications contains all the material necessary for a first year graduate or advanced undergraduate course on numerical linear algebra with numerous applications to engineering and science. With a unified presentation of computation, basic algorithm analysis, and numerical methods to compute solutions, this book is ideal for solving real-world problems. It provides necessary mathematical background information for
DEFF Research Database (Denmark)
Schmidt, Thomas Lundsgaard; Thomsen, Klaus
2015-01-01
We consider a construction of $C^*$-algebras from continuous piecewise monotone maps on the circle which generalizes the crossed product construction for homeomorphisms and more generally the construction of Renault, Deaconu and Anantharaman-Delaroche for local homeomorphisms. Assuming that the map...... is surjective and not locally injective we give necessary and sufficient conditions for the simplicity of the $C^*$-algebra and show that it is then a Kirchberg algebra. We provide tools for the calculation of the K-theory groups and turn them into an algorithmic method for Markov maps....
Gauss Elimination: Workhorse of Linear Algebra.
1995-08-05
linear algebra computation for solving systems, computing determinants and determining the rank of matrix. All of these are discussed in varying contexts. These include different arithmetic or algebraic setting such as integer arithmetic or polynomial rings as well as conventional real (floating-point) arithmetic. These have effects on both accuracy and complexity analyses of the algorithm. These, too, are covered here. The impact of modern parallel computer architecture on GE is also
Indian Academy of Sciences (India)
algorithm design technique called 'divide-and-conquer'. One of ... Turtle graphics, September. 1996. 5. ... whole list named 'PO' is a pointer to the first element of the list; ..... Program for computing matrices X and Y and placing the result in C *).
Indian Academy of Sciences (India)
algorithm that it is implicitly understood that we know how to generate the next natural ..... Explicit comparisons are made in line (1) where maximum and minimum is ... It can be shown that the function T(n) = 3/2n -2 is the solution to the above ...
Abrams, Gene; Siles Molina, Mercedes
2017-01-01
This book offers a comprehensive introduction by three of the leading experts in the field, collecting fundamental results and open problems in a single volume. Since Leavitt path algebras were first defined in 2005, interest in these algebras has grown substantially, with ring theorists as well as researchers working in graph C*-algebras, group theory and symbolic dynamics attracted to the topic. Providing a historical perspective on the subject, the authors review existing arguments, establish new results, and outline the major themes and ring-theoretic concepts, such as the ideal structure, Z-grading and the close link between Leavitt path algebras and graph C*-algebras. The book also presents key lines of current research, including the Algebraic Kirchberg Phillips Question, various additional classification questions, and connections to noncommutative algebraic geometry. Leavitt Path Algebras will appeal to graduate students and researchers working in the field and related areas, such as C*-algebras and...
Rigorous lower bound on the dynamic critical exponent of some multilevel Swendsen-Wang algorithms
International Nuclear Information System (INIS)
Li, X.; Sokal, A.D.
1991-01-01
We prove the rigorous lower bound z exp ≥α/ν for the dynamic critical exponent of a broad class of multilevel (or ''multigrid'') variants of the Swendsen-Wang algorithm. This proves that such algorithms do suffer from critical slowing down. We conjecture that such algorithms in fact lie in the same dynamic universality class as the stanard Swendsen-Wang algorithm
Multigrid solution of incompressible turbulent flows by using two-equation turbulence models
Energy Technology Data Exchange (ETDEWEB)
Zheng, X.; Liu, C. [Front Range Scientific Computations, Inc., Denver, CO (United States); Sung, C.H. [David Taylor Model Basin, Bethesda, MD (United States)
1996-12-31
Most of practical flows are turbulent. From the interest of engineering applications, simulation of realistic flows is usually done through solution of Reynolds-averaged Navier-Stokes equations and turbulence model equations. It has been widely accepted that turbulence modeling plays a very important role in numerical simulation of practical flow problem, particularly when the accuracy is of great concern. Among the most used turbulence models today, two-equation models appear to be favored for the reason that they are more general than algebraic models and affordable with current available computer resources. However, investigators using two-equation models seem to have been more concerned with the solution of N-S equations. Less attention is paid to the solution method for the turbulence model equations. In most cases, the turbulence model equations are loosely coupled with N-S equations, multigrid acceleration is only applied to the solution of N-S equations due to perhaps the fact the turbulence model equations are source-term dominant and very stiff in sublayer region.
Samuel, Pierre
2008-01-01
Algebraic number theory introduces students not only to new algebraic notions but also to related concepts: groups, rings, fields, ideals, quotient rings and quotient fields, homomorphisms and isomorphisms, modules, and vector spaces. Author Pierre Samuel notes that students benefit from their studies of algebraic number theory by encountering many concepts fundamental to other branches of mathematics - algebraic geometry, in particular.This book assumes a knowledge of basic algebra but supplements its teachings with brief, clear explanations of integrality, algebraic extensions of fields, Gal
Boicescu, V; Georgescu, G; Rudeanu, S
1991-01-01
The Lukasiewicz-Moisil algebras were created by Moisil as an algebraic counterpart for the many-valued logics of Lukasiewicz. The theory of LM-algebras has developed to a considerable extent both as an algebraic theory of intrinsic interest and in view of its applications to logic and switching theory.This book gives an overview of the theory, comprising both classical results and recent contributions, including those of the authors. N-valued and &THgr;-valued algebras are presented, as well as &THgr;-algebras with negation.Mathematicians interested in lattice theory or symbolic logic, and computer scientists, will find in this monograph stimulating material for further research.
Introduction to quantum algebras
International Nuclear Information System (INIS)
Kibler, M.R.
1992-09-01
The concept of a quantum algebra is made easy through the investigation of the prototype algebras u qp (2), su q (2) and u qp (1,1). The latter quantum algebras are introduced as deformations of the corresponding Lie algebras; this is achieved in a simple way by means of qp-bosons. The Hopf algebraic structure of u qp (2) is also discussed. The basic ingredients for the representation theory of u qp (2) are given. Finally, in connection with the quantum algebra u qp (2), the qp-analogues of the harmonic oscillator are discussed and of the (spherical and hyperbolical) angular momenta. (author) 50 refs
Pérez López, César
2014-01-01
MATLAB is a high-level language and environment for numerical computation, visualization, and programming. Using MATLAB, you can analyze data, develop algorithms, and create models and applications. The language, tools, and built-in math functions enable you to explore multiple approaches and reach a solution faster than with spreadsheets or traditional programming languages, such as C/C++ or Java. MATLAB Matrix Algebra introduces you to the MATLAB language with practical hands-on instructions and results, allowing you to quickly achieve your goals. Starting with a look at symbolic and numeric variables, with an emphasis on vector and matrix variables, you will go on to examine functions and operations that support vectors and matrices as arguments, including those based on analytic parent functions. Computational methods for finding eigenvalues and eigenvectors of matrices are detailed, leading to various matrix decompositions. Applications such as change of bases, the classification of quadratic forms and ...
Indian Academy of Sciences (India)
will become clear in the next article when we discuss a simple logo like programming language. ... Rod B may be used as an auxiliary store. The problem is to find an algorithm which performs this task. ... No disks are moved from A to Busing C as auxiliary rod. • move _disk (A, C);. (No + l)th disk is moved from A to C directly ...
Non-freely generated W-algebras and construction of N=2 super W-algebras
International Nuclear Information System (INIS)
Blumenhagen, R.
1994-07-01
Firstly, we investigate the origin of the bosonic W-algebras W(2, 3, 4, 5), W(2, 4, 6) and W(2, 4, 6) found earlier by direct construction. We present a coset construction for all three examples leading to a new type of finitely, non-freely generated quantum W-algebras, which we call unifying W-algebras. Secondly, we develop a manifest covariant formalism to construct N = 2 super W-algebras explicitly on a computer. Applying this algorithm enables us to construct the first four examples of N = 2 super W-algebras with two generators and the N = 2 super W 4 algebra involving three generators. The representation theory of the former ones shows that all examples could be divided into four classes, the largest one containing the N = 2 special type of spectral flow algebras. Besides the W-algebra of the CP(3) Kazama-Suzuki coset model, the latter example with three generators discloses a second solution which could also be explained as a unifying W-algebra for the CP(n) models. (orig.)
Costiner, Sorin; Taasan, Shlomo
1994-01-01
This paper presents multigrid (MG) techniques for nonlinear eigenvalue problems (EP) and emphasizes an MG algorithm for a nonlinear Schrodinger EP. The algorithm overcomes the mentioned difficulties combining the following techniques: an MG projection coupled with backrotations for separation of solutions and treatment of difficulties related to clusters of close and equal eigenvalues; MG subspace continuation techniques for treatment of the nonlinearity; an MG simultaneous treatment of the eigenvectors at the same time with the nonlinearity and with the global constraints. The simultaneous MG techniques reduce the large number of self consistent iterations to only a few or one MG simultaneous iteration and keep the solutions in a right neighborhood where the algorithm converges fast.
Towards a multigrid scheme in SU(2) lattice gauge theory
International Nuclear Information System (INIS)
Gutbrod, F.
1992-12-01
The task of constructing a viable updating multigrid scheme for SU(2) lattice gauge theory is discussed in connection with the classical eigenvalue problem. For a nonlocal overrelaxation Monte Carlo update step, the central numerical problem is the search for the minimum of a quadratic approximation to the action under nonlocal constraints. Here approximate eigenfunctions are essential to reduce the numerical work, and these eigenfunctions are to be constructed with multigrid techniques. A simple implementation on asymmetric lattices is described, where the grids are restricted to 3-dimensional hyperplanes. The scheme is shown to be moderately successful in the early stages of the updating history (starting from a cold configuration). The main results of another, less asymmetric scheme are presented briefly. (orig.)
Generalized EMV-Effect Algebras
Borzooei, R. A.; Dvurečenskij, A.; Sharafi, A. H.
2018-04-01
Recently in Dvurečenskij and Zahiri (2017), new algebraic structures, called EMV-algebras which generalize both MV-algebras and generalized Boolean algebras, were introduced. We present equivalent conditions for EMV-algebras. In addition, we define a partial algebraic structure, called a generalized EMV-effect algebra, which is close to generalized MV-effect algebras. Finally, we show that every generalized EMV-effect algebra is either an MV-effect algebra or can be embedded into an MV-effect algebra as a maximal ideal.
Construction and decoding of a class of algebraic geometry codes
DEFF Research Database (Denmark)
Justesen, Jørn; Larsen, Knud J.; Jensen, Helge Elbrønd
1989-01-01
A class of codes derived from algebraic plane curves is constructed. The concepts and results from algebraic geometry that were used are explained in detail; no further knowledge of algebraic geometry is needed. Parameters, generator and parity-check matrices are given. The main result is a decod...... is a decoding algorithm which turns out to be a generalization of the Peterson algorithm for decoding BCH decoder codes......A class of codes derived from algebraic plane curves is constructed. The concepts and results from algebraic geometry that were used are explained in detail; no further knowledge of algebraic geometry is needed. Parameters, generator and parity-check matrices are given. The main result...
Multigrid time-accurate integration of Navier-Stokes equations
Arnone, Andrea; Liou, Meng-Sing; Povinelli, Louis A.
1993-01-01
Efficient acceleration techniques typical of explicit steady-state solvers are extended to time-accurate calculations. Stability restrictions are greatly reduced by means of a fully implicit time discretization. A four-stage Runge-Kutta scheme with local time stepping, residual smoothing, and multigridding is used instead of traditional time-expensive factorizations. Some applications to natural and forced unsteady viscous flows show the capability of the procedure.
Asveld, P.R.J.
1976-01-01
Operaties op formele talen geven aanleiding tot bijbehorende operatoren op families talen. Bepaalde onderwerpen uit de algebra (universele algebra, tralies, partieel geordende monoiden) kunnen behulpzaam zijn in de studie van verzamelingen van dergelijke operatoren.
Rudiments of algebraic geometry
Jenner, WE
2017-01-01
Aimed at advanced undergraduate students of mathematics, this concise text covers the basics of algebraic geometry. Topics include affine spaces, projective spaces, rational curves, algebraic sets with group structure, more. 1963 edition.
Algorithmic Verification of Linearizability for Ordinary Differential Equations
Lyakhov, Dmitry A.; Gerdt, Vladimir P.; Michels, Dominik L.
2017-01-01
one by a point transformation of the dependent and independent variables. The first algorithm is based on a construction of the Lie point symmetry algebra and on the computation of its derived algebra. The second algorithm exploits the differential
Jönsthövel, T.B.; Van Gijzen, M.B.; MacLachlan, S.; Vuik, C.; Scarpas, A.
2012-01-01
Many applications in computational science and engineering concern composite materials, which are characterized by large discontinuities in the material properties. Such applications require fine-scale finite-element meshes, which lead to large linear systems that are challenging to solve with
Cylindric-like algebras and algebraic logic
Ferenczi, Miklós; Németi, István
2013-01-01
Algebraic logic is a subject in the interface between logic, algebra and geometry, it has strong connections with category theory and combinatorics. Tarski’s quest for finding structure in logic leads to cylindric-like algebras as studied in this book, they are among the main players in Tarskian algebraic logic. Cylindric algebra theory can be viewed in many ways: as an algebraic form of definability theory, as a study of higher-dimensional relations, as an enrichment of Boolean Algebra theory, or, as logic in geometric form (“cylindric” in the name refers to geometric aspects). Cylindric-like algebras have a wide range of applications, in, e.g., natural language theory, data-base theory, stochastics, and even in relativity theory. The present volume, consisting of 18 survey papers, intends to give an overview of the main achievements and new research directions in the past 30 years, since the publication of the Henkin-Monk-Tarski monographs. It is dedicated to the memory of Leon Henkin.
Categories and Commutative Algebra
Salmon, P
2011-01-01
L. Badescu: Sur certaines singularites des varietes algebriques.- D.A. Buchsbaum: Homological and commutative algebra.- S. Greco: Anelli Henseliani.- C. Lair: Morphismes et structures algebriques.- B.A. Mitchell: Introduction to category theory and homological algebra.- R. Rivet: Anneaux de series formelles et anneaux henseliens.- P. Salmon: Applicazioni della K-teoria all'algebra commutativa.- M. Tierney: Axiomatic sheaf theory: some constructions and applications.- C.B. Winters: An elementary lecture on algebraic spaces.
Abstract algebra for physicists
International Nuclear Information System (INIS)
Zeman, J.
1975-06-01
Certain recent models of composite hadrons involve concepts and theorems from abstract algebra which are unfamiliar to most theoretical physicists. The algebraic apparatus needed for an understanding of these models is summarized here. Particular emphasis is given to algebraic structures which are not assumed to be associative. (2 figures) (auth)
Combinatorial commutative algebra
Miller, Ezra
2005-01-01
Offers an introduction to combinatorial commutative algebra, focusing on combinatorial techniques for multigraded polynomial rings, semigroup algebras, and determined rings. The chapters in this work cover topics ranging from homological invariants of monomial ideals and their polyhedral resolutions, to tools for studying algebraic varieties.
Local multigrid mesh refinement in view of nuclear fuel 3D modelling in pressurised water reactors
International Nuclear Information System (INIS)
Barbie, L.
2013-01-01
The aim of this study is to improve the performances, in terms of memory space and computational time, of the current modelling of the Pellet-Cladding mechanical Interaction (PCI), complex phenomenon which may occurs during high power rises in pressurised water reactors. Among the mesh refinement methods - methods dedicated to efficiently treat local singularities - a local multi-grid approach was selected because it enables the use of a black-box solver while dealing few degrees of freedom at each level. The Local Defect Correction (LDC) method, well suited to a finite element discretization, was first analysed and checked in linear elasticity, on configurations resulting from the PCI, since its use in solid mechanics is little widespread. Various strategies concerning the implementation of the multilevel algorithm were also compared. Coupling the LDC method with the Zienkiewicz-Zhu a posteriori error estimator in order to automatically detect the zones to be refined, was then tested. Performances obtained on two-dimensional and three-dimensional cases are very satisfactory, since the algorithm proposed is more efficient than h-adaptive refinement methods. Lastly, the LDC algorithm was extended to nonlinear mechanics. Space/time refinement as well as transmission of the initial conditions during the re-meshing step were looked at. The first results obtained are encouraging and show the interest of using the LDC method for PCI modelling. (author) [fr
Hougardy, Stefan
2016-01-01
Algorithms play an increasingly important role in nearly all fields of mathematics. This book allows readers to develop basic mathematical abilities, in particular those concerning the design and analysis of algorithms as well as their implementation. It presents not only fundamental algorithms like the sieve of Eratosthenes, the Euclidean algorithm, sorting algorithms, algorithms on graphs, and Gaussian elimination, but also discusses elementary data structures, basic graph theory, and numerical questions. In addition, it provides an introduction to programming and demonstrates in detail how to implement algorithms in C++. This textbook is suitable for students who are new to the subject and covers a basic mathematical lecture course, complementing traditional courses on analysis and linear algebra. Both authors have given this "Algorithmic Mathematics" course at the University of Bonn several times in recent years.
Applied linear algebra and matrix analysis
Shores, Thomas S
2018-01-01
In its second edition, this textbook offers a fresh approach to matrix and linear algebra. Its blend of theory, computational exercises, and analytical writing projects is designed to highlight the interplay between these aspects of an application. This approach places special emphasis on linear algebra as an experimental science that provides tools for solving concrete problems. The second edition’s revised text discusses applications of linear algebra like graph theory and network modeling methods used in Google’s PageRank algorithm. Other new materials include modeling examples of diffusive processes, linear programming, image processing, digital signal processing, and Fourier analysis. These topics are woven into the core material of Gaussian elimination and other matrix operations; eigenvalues, eigenvectors, and discrete dynamical systems; and the geometrical aspects of vector spaces. Intended for a one-semester undergraduate course without a strict calculus prerequisite, Applied Linear Algebra and M...
International Nuclear Information System (INIS)
Krivonos, S.O.; Sorin, A.S.
1994-06-01
We show that the Zamolodchikov's and Polyakov-Bershadsky nonlinear algebras W 3 and W (2) 3 can be embedded as subalgebras into some linear algebras with finite set of currents. Using these linear algebras we find new field realizations of W (2) 3 and W 3 which could be a starting point for constructing new versions of W-string theories. We also reveal a number of hidden relationships between W 3 and W (2) 3 . We conjecture that similar linear algebras can exist for other W-algebra as well. (author). 10 refs
International Nuclear Information System (INIS)
Hudetz, T.
1989-01-01
As a 'by-product' of the Connes-Narnhofer-Thirring theory of dynamical entropy for (originally non-Abelian) nuclear C * -algebras, the well-known variational principle for topological entropy is eqivalently reformulated in purly algebraically defined terms for (separable) Abelian C * -algebras. This 'algebraic variational principle' should not only nicely illustrate the 'feed-back' of methods developed for quantum dynamical systems to the classical theory, but it could also be proved directly by 'algebraic' methods and could thus further simplify the original proof of the variational principle (at least 'in principle'). 23 refs. (Author)
Uzawa smoother in multigrid for the coupleD porous medium and stokes flow system
P. Luo (Peiyao); C. Rodrigo (Carmen); F.J. Gaspar Lorenz (Franscisco); C.W. Oosterlee (Kees)
2017-01-01
textabstractThe multigrid solution of coupled porous media and Stokes flow problems is considered. The Darcy equation as the saturated porous medium model is coupled to the Stokes equations by means of appropriate interface conditions. We focus on an efficient multigrid solution technique for the
Multigrid for high dimensional elliptic partial differential equations on non-equidistant grids
bin Zubair, H.; Oosterlee, C.E.; Wienands, R.
2006-01-01
This work presents techniques, theory and numbers for multigrid in a general d-dimensional setting. The main focus is the multigrid convergence for high-dimensional partial differential equations (PDEs). As a model problem we have chosen the anisotropic diffusion equation, on a unit hypercube. We
Multigrid solution of the convection-diffusion equation with high-Reynolds number
Energy Technology Data Exchange (ETDEWEB)
Zhang, Jun [George Washington Univ., Washington, DC (United States)
1996-12-31
A fourth-order compact finite difference scheme is employed with the multigrid technique to solve the variable coefficient convection-diffusion equation with high-Reynolds number. Scaled inter-grid transfer operators and potential on vectorization and parallelization are discussed. The high-order multigrid method is unconditionally stable and produces solution of 4th-order accuracy. Numerical experiments are included.
Lectures on algebraic statistics
Drton, Mathias; Sullivant, Seth
2009-01-01
How does an algebraic geometer studying secant varieties further the understanding of hypothesis tests in statistics? Why would a statistician working on factor analysis raise open problems about determinantal varieties? Connections of this type are at the heart of the new field of "algebraic statistics". In this field, mathematicians and statisticians come together to solve statistical inference problems using concepts from algebraic geometry as well as related computational and combinatorial techniques. The goal of these lectures is to introduce newcomers from the different camps to algebraic statistics. The introduction will be centered around the following three observations: many important statistical models correspond to algebraic or semi-algebraic sets of parameters; the geometry of these parameter spaces determines the behaviour of widely used statistical inference procedures; computational algebraic geometry can be used to study parameter spaces and other features of statistical models.
International Nuclear Information System (INIS)
Goddard, Peter
1990-01-01
The algebra of the group of conformal transformations in two dimensions consists of two commuting copies of the Virasoro algebra. In many mathematical and physical contexts, the representations of ν which are relevant satisfy two conditions: they are unitary and they have the ''positive energy'' property that L o is bounded below. In an irreducible unitary representation the central element c takes a fixed real value. In physical contexts, the value of c is a characteristic of a theory. If c < 1, it turns out that the conformal algebra is sufficient to ''solve'' the theory, in the sense of relating the calculation of the infinite set of physically interesting quantities to a finite subset which can be handled in principle. For c ≥ 1, this is no longer the case for the algebra alone and one needs some sort of extended conformal algebra, such as the superconformal algebra. It is these algebras that this paper aims at addressing. (author)
Algebraic conformal field theory
International Nuclear Information System (INIS)
Fuchs, J.; Nationaal Inst. voor Kernfysica en Hoge-Energiefysica
1991-11-01
Many conformal field theory features are special versions of structures which are present in arbitrary 2-dimensional quantum field theories. So it makes sense to describe 2-dimensional conformal field theories in context of algebraic theory of superselection sectors. While most of the results of the algebraic theory are rather abstract, conformal field theories offer the possibility to work out many formulae explicitly. In particular, one can construct the full algebra A-bar of global observables and the endomorphisms of A-bar which represent the superselection sectors. Some explicit results are presented for the level 1 so(N) WZW theories; the algebra A-bar is found to be the enveloping algebra of a Lie algebra L-bar which is an extension of the chiral symmetry algebra of the WZW theory. (author). 21 refs., 6 figs
International Nuclear Information System (INIS)
Feigin, B.L.; Semikhatov, A.M.
2004-01-01
We construct W-algebra generalizations of the sl-circumflex(2) algebra-W algebras W n (2) generated by two currents E and F with the highest pole of order n in their OPE. The n=3 term in this series is the Bershadsky-Polyakov W 3 (2) algebra. We define these algebras as a centralizer (commutant) of the Uqs-bar (n vertical bar 1) quantum supergroup and explicitly find the generators in a factored, 'Miura-like' form. Another construction of the W n (2) algebras is in terms of the coset sl-circumflex(n vertical bar 1)/sl-circumflex(n). The relation between the two constructions involves the 'duality' (k+n-1)(k'+n-1)=1 between levels k and k' of two sl-circumflex(n) algebras
Bicovariant quantum algebras and quantum Lie algebras
International Nuclear Information System (INIS)
Schupp, P.; Watts, P.; Zumino, B.
1993-01-01
A bicovariant calculus of differential operators on a quantum group is constructed in a natural way, using invariant maps from Fun(G q ) to U q g, given by elements of the pure braid group. These operators - the 'reflection matrix' Y= triple bond L + SL - being a special case - generate algebras that linearly close under adjoint actions, i.e. they form generalized Lie algebras. We establish the connection between the Hopf algebra formulation of the calculus and a formulation in compact matrix form which is quite powerful for actual computations and as applications we find the quantum determinant and an orthogonality relation for Y in SO q (N). (orig.)
The Boolean algebra and central Galois algebras
Directory of Open Access Journals (Sweden)
George Szeto
2001-01-01
Full Text Available Let B be a Galois algebra with Galois group G, Jg={b∈B∣bx=g(xb for all x∈B} for g∈G, and BJg=Beg for a central idempotent eg. Then a relation is given between the set of elements in the Boolean algebra (Ba,≤ generated by {0,eg∣g∈G} and a set of subgroups of G, and a central Galois algebra Be with a Galois subgroup of G is characterized for an e∈Ba.
Solution of systems of linear algebraic equations by the method of summation of divergent series
International Nuclear Information System (INIS)
Kirichenko, G.A.; Korovin, Ya.S.; Khisamutdinov, M.V.; Shmojlov, V.I.
2015-01-01
A method for solving systems of linear algebraic equations has been proposed on the basis on the summation of the corresponding continued fractions. The proposed algorithm for solving systems of linear algebraic equations is classified as direct algorithms providing an exact solution in a finite number of operations. Examples of solving systems of linear algebraic equations have been presented and the effectiveness of the algorithm has been estimated [ru
Nonflexible Lie-admissible algebras
International Nuclear Information System (INIS)
Myung, H.C.
1978-01-01
We discuss the structure of Lie-admissible algebras which are defined by nonflexible identities. These algebras largely arise from the antiflexible algebras, 2-varieties and associator dependent algebras. The nonflexible Lie-admissible algebras in our discussion are in essence byproducts of the study of nonassociative algebras defined by identities of degree 3. The main purpose is to discuss the classification of simple Lie-admissible algebras of nonflexible type
Recoupling Lie algebra and universal ω-algebra
International Nuclear Information System (INIS)
Joyce, William P.
2004-01-01
We formulate the algebraic version of recoupling theory suitable for commutation quantization over any gradation. This gives a generalization of graded Lie algebra. Underlying this is the new notion of an ω-algebra defined in this paper. ω-algebra is a generalization of algebra that goes beyond nonassociativity. We construct the universal enveloping ω-algebra of recoupling Lie algebras and prove a generalized Poincare-Birkhoff-Witt theorem. As an example we consider the algebras over an arbitrary recoupling of Z n graded Heisenberg Lie algebra. Finally we uncover the usual coalgebra structure of a universal envelope and substantiate its Hopf structure
Hurwitz Algebras and the Octonion Algebra
Burdik, Čestmir; Catto, Sultan
2018-02-01
We explore some consequences of a theory of internal symmetries for elementary particles constructed on exceptional quantum mechanical spaces based on Jordan algebra formulation that admit exceptional groups as gauge groups.
A program for constructing finitely presented Lie algebras and superalgebras
International Nuclear Information System (INIS)
Gerdt, V.P.; Kornyak, V.V.
1997-01-01
The purpose of this paper is to describe a C program FPLSA for investigating finitely presented Lie algebras and superalgebras. The underlying algorithm is based on constructing the complete set of relations called also standard basis or Groebner basis of ideal of free Lie (super) algebra generated by the input set of relations. The program may be used, in particular, to compute the Lie (super)algebra basis elements and its structure constants, to classify the finitely presented algebras depending on the values of parameters in the relations, and to construct the Hilbert series. These problems are illustrated by examples. (orig.)
Extended Virasoro algebra and algebra of area preserving diffeomorphisms
International Nuclear Information System (INIS)
Arakelyan, T.A.
1990-01-01
The algebra of area preserving diffeomorphism plays an important role in the theory of relativistic membranes. It is pointed out that the relation between this algebra and the extended Virasoro algebra associated with the generalized Kac-Moody algebras G(T 2 ). The highest weight representation of these infinite-dimensional algebras as well as of their subalgebras is studied. 5 refs
Linear algebra meets Lie algebra: the Kostant-Wallach theory
Shomron, Noam; Parlett, Beresford N.
2008-01-01
In two languages, Linear Algebra and Lie Algebra, we describe the results of Kostant and Wallach on the fibre of matrices with prescribed eigenvalues of all leading principal submatrices. In addition, we present a brief introduction to basic notions in Algebraic Geometry, Integrable Systems, and Lie Algebra aimed at specialists in Linear Algebra.
Multigrid Reduction in Time for Nonlinear Parabolic Problems
Energy Technology Data Exchange (ETDEWEB)
Falgout, R. D. [Lawrence Livermore National Lab. (LLNL), Livermore, CA (United States); Manteuffel, T. A. [Univ. of Colorado, Boulder, CO (United States); O' Neill, B. [Univ. of Colorado, Boulder, CO (United States); Schroder, J. B. [Lawrence Livermore National Lab. (LLNL), Livermore, CA (United States)
2016-01-04
The need for parallel-in-time is being driven by changes in computer architectures, where future speed-ups will be available through greater concurrency, but not faster clock speeds, which are stagnant.This leads to a bottleneck for sequential time marching schemes, because they lack parallelism in the time dimension. Multigrid Reduction in Time (MGRIT) is an iterative procedure that allows for temporal parallelism by utilizing multigrid reduction techniques and a multilevel hierarchy of coarse time grids. MGRIT has been shown to be effective for linear problems, with speedups of up to 50 times. The goal of this work is the efficient solution of nonlinear problems with MGRIT, where efficient is defined as achieving similar performance when compared to a corresponding linear problem. As our benchmark, we use the p-Laplacian, where p = 4 corresponds to a well-known nonlinear diffusion equation and p = 2 corresponds to our benchmark linear diffusion problem. When considering linear problems and implicit methods, the use of optimal spatial solvers such as spatial multigrid imply that the cost of one time step evaluation is fixed across temporal levels, which have a large variation in time step sizes. This is not the case for nonlinear problems, where the work required increases dramatically on coarser time grids, where relatively large time steps lead to worse conditioned nonlinear solves and increased nonlinear iteration counts per time step evaluation. This is the key difficulty explored by this paper. We show that by using a variety of strategies, most importantly, spatial coarsening and an alternate initial guess to the nonlinear time-step solver, we can reduce the work per time step evaluation over all temporal levels to a range similar with the corresponding linear problem. This allows for parallel scaling behavior comparable to the corresponding linear problem.
Damage mapping in structural health monitoring using a multi-grid architecture
Energy Technology Data Exchange (ETDEWEB)
Mathews, V. John [Dept. of Electrical and Computer Engineering, University of Utah, Salt Lake City, UT 84112 (United States)
2015-03-31
This paper presents a multi-grid architecture for tomography-based damage mapping of composite aerospace structures. The system employs an array of piezo-electric transducers bonded on the structure. Each transducer may be used as an actuator as well as a sensor. The structure is excited sequentially using the actuators and the guided waves arriving at the sensors in response to the excitations are recorded for further analysis. The sensor signals are compared to their baseline counterparts and a damage index is computed for each actuator-sensor pair. These damage indices are then used as inputs to the tomographic reconstruction system. Preliminary damage maps are reconstructed on multiple coordinate grids defined on the structure. These grids are shifted versions of each other where the shift is a fraction of the spatial sampling interval associated with each grid. These preliminary damage maps are then combined to provide a reconstruction that is more robust to measurement noise in the sensor signals and the ill-conditioned problem formulation for single-grid algorithms. Experimental results on a composite structure with complexity that is representative of aerospace structures included in the paper demonstrate that for sufficiently high sensor densities, the algorithm of this paper is capable of providing damage detection and characterization with accuracy comparable to traditional C-scan and A-scan-based ultrasound non-destructive inspection systems quickly and without human supervision.
Forward error correction based on algebraic-geometric theory
A Alzubi, Jafar; M Chen, Thomas
2014-01-01
This book covers the design, construction, and implementation of algebraic-geometric codes from Hermitian curves. Matlab simulations of algebraic-geometric codes and Reed-Solomon codes compare their bit error rate using different modulation schemes over additive white Gaussian noise channel model. Simulation results of Algebraic-geometric codes bit error rate performance using quadrature amplitude modulation (16QAM and 64QAM) are presented for the first time and shown to outperform Reed-Solomon codes at various code rates and channel models. The book proposes algebraic-geometric block turbo codes. It also presents simulation results that show an improved bit error rate performance at the cost of high system complexity due to using algebraic-geometric codes and Chase-Pyndiah’s algorithm simultaneously. The book proposes algebraic-geometric irregular block turbo codes (AG-IBTC) to reduce system complexity. Simulation results for AG-IBTCs are presented for the first time.
Multigrid methods for fully implicit oil reservoir simulation
Energy Technology Data Exchange (ETDEWEB)
Molenaar, J.
1995-12-31
In this paper, the authors consider the simultaneous flow of oil and water in reservoir rock. This displacement process is modeled by two basic equations the material balance or continuity equations, and the equation of motion (Darcy`s law). For the numerical solution of this system of nonlinear partial differential equations, there are two approaches: the fully implicit or simultaneous solution method, and the sequential solution method. In this paper, the authors consider the possibility of applying multigrid methods for the iterative solution of the systems of nonlinear equations.
Fast multigrid solution of the advection problem with closed characteristics
Energy Technology Data Exchange (ETDEWEB)
Yavneh, I. [Israel Inst. of Technology, Haifa (Israel); Venner, C.H. [Univ. of Twente, Enschede (Netherlands); Brandt, A. [Weizmann Inst. of Science, Rehovot (Israel)
1996-12-31
The numerical solution of the advection-diffusion problem in the inviscid limit with closed characteristics is studied as a prelude to an efficient high Reynolds-number flow solver. It is demonstrated by a heuristic analysis and numerical calculations that using upstream discretization with downstream relaxation-ordering and appropriate residual weighting in a simple multigrid V cycle produces an efficient solution process. We also derive upstream finite-difference approximations to the advection operator, whose truncation terms approximate {open_quotes}physical{close_quotes} (Laplacian) viscosity, thus avoiding spurious solutions to the homogeneous problem when the artificial diffusivity dominates the physical viscosity.
International Nuclear Information System (INIS)
Takao, Masaru
1989-01-01
We review W-algebras which are generated by stress tensor and primary fields. Associativity plays an important role in determining the extended algebra and further implies the algebras to exist for special values of central charges. Explicitly constructing the algebras including primary fields of spin less than 4, we investigate the closure structure of the Jacobi identity of the extended algebras. (author)
Representations of quantum bicrossproduct algebras
International Nuclear Information System (INIS)
Arratia, Oscar; Olmo, Mariano A del
2002-01-01
We present a method to construct induced representations of quantum algebras which have a bicrossproduct structure. We apply this procedure to some quantum kinematical algebras in (1+1) dimensions with this kind of structure: null-plane quantum Poincare algebra, non-standard quantum Galilei algebra and quantum κ-Galilei algebra
Borzooei, R. A.; Dudek, W. A.; Koohestani, N.
2006-01-01
We study hyper BCC-algebras which are a common generalization of BCC-algebras and hyper BCK-algebras. In particular, we investigate different types of hyper BCC-ideals and describe the relationship among them. Next, we calculate all nonisomorphic 22 hyper BCC-algebras of order 3 of which only three are not hyper BCK-algebras.
Directory of Open Access Journals (Sweden)
R. A. Borzooei
2006-01-01
Full Text Available We study hyper BCC-algebras which are a common generalization of BCC-algebras and hyper BCK-algebras. In particular, we investigate different types of hyper BCC-ideals and describe the relationship among them. Next, we calculate all nonisomorphic 22 hyper BCC-algebras of order 3 of which only three are not hyper BCK-algebras.
Givant, Steven
2017-01-01
This monograph details several different methods for constructing simple relation algebras, many of which are new with this book. By drawing these seemingly different methods together, all are shown to be aspects of one general approach, for which several applications are given. These tools for constructing and analyzing relation algebras are of particular interest to mathematicians working in logic, algebraic logic, or universal algebra, but will also appeal to philosophers and theoretical computer scientists working in fields that use mathematics. The book is written with a broad audience in mind and features a careful, pedagogical approach; an appendix contains the requisite background material in relation algebras. Over 400 exercises provide ample opportunities to engage with the material, making this a monograph equally appropriate for use in a special topics course or for independent study. Readers interested in pursuing an extended background study of relation algebras will find a comprehensive treatme...
Iachello, Francesco
2015-01-01
This course-based primer provides an introduction to Lie algebras and some of their applications to the spectroscopy of molecules, atoms, nuclei and hadrons. In the first part, it concisely presents the basic concepts of Lie algebras, their representations and their invariants. The second part includes a description of how Lie algebras are used in practice in the treatment of bosonic and fermionic systems. Physical applications considered include rotations and vibrations of molecules (vibron model), collective modes in nuclei (interacting boson model), the atomic shell model, the nuclear shell model, and the quark model of hadrons. One of the key concepts in the application of Lie algebraic methods in physics, that of spectrum generating algebras and their associated dynamic symmetries, is also discussed. The book highlights a number of examples that help to illustrate the abstract algebraic definitions and includes a summary of many formulas of practical interest, such as the eigenvalues of Casimir operators...
Twisted classical Poincare algebras
International Nuclear Information System (INIS)
Lukierski, J.; Ruegg, H.; Tolstoy, V.N.; Nowicki, A.
1993-11-01
We consider the twisting of Hopf structure for classical enveloping algebra U(g), where g is the inhomogeneous rotations algebra, with explicite formulae given for D=4 Poincare algebra (g=P 4 ). The comultiplications of twisted U F (P 4 ) are obtained by conjugating primitive classical coproducts by F element of U(c)xU(c), where c denotes any Abelian subalgebra of P 4 , and the universal R-matrices for U F (P 4 ) are triangular. As an example we show that the quantum deformation of Poincare algebra recently proposed by Chaichian and Demiczev is a twisted classical Poincare algebra. The interpretation of twisted Poincare algebra as describing relativistic symmetries with clustered 2-particle states is proposed. (orig.)
A Linear Algebra Measure of Cluster Quality.
Mather, Laura A.
2000-01-01
Discussion of models for information retrieval focuses on an application of linear algebra to text clustering, namely, a metric for measuring cluster quality based on the theory that cluster quality is proportional to the number of terms that are disjoint across the clusters. Explains term-document matrices and clustering algorithms. (Author/LRW)
Recent results in the decoding of Algebraic geometry codes
DEFF Research Database (Denmark)
Høholdt, Tom; Jensen, Helge Elbrønd; Nielsen, Rasmus Refslund
1998-01-01
We analyse the known decoding algorithms for algebraic geometry codes in the case where the number of errors is [(dFR-1)/2]+1, where dFR is the Feng-Rao distance......We analyse the known decoding algorithms for algebraic geometry codes in the case where the number of errors is [(dFR-1)/2]+1, where dFR is the Feng-Rao distance...
Fast Bitwise Implementation of the Algebraic Normal Form Transform
Bakoev, Valentin
2017-01-01
The representation of Boolean functions by their algebraic normal forms (ANFs) is very important for cryptography, coding theory and other scientific areas. The ANFs are used in computing the algebraic degree of S-boxes, some other cryptographic criteria and parameters of errorcorrecting codes. Their applications require these criteria and parameters to be computed by fast algorithms. Hence the corresponding ANFs should also be obtained by fast algorithms. Here we continue o...
Symbolic Reachability for Process Algebras with Recursive Data Types
Blom, Stefan; van de Pol, Jan Cornelis; Fitzgerald, J.S.; Haxthausen, A.E.; Yenigun, H.
2008-01-01
In this paper, we present a symbolic reachability algorithm for process algebras with recursive data types. Like the various saturation based algorithms of Ciardo et al, the algorithm is based on partitioning of the transition relation into events whose influence is local. As new features, our
Directory of Open Access Journals (Sweden)
Frank Roumen
2017-01-01
Full Text Available We will define two ways to assign cohomology groups to effect algebras, which occur in the algebraic study of quantum logic. The first way is based on Connes' cyclic cohomology. The resulting cohomology groups are related to the state space of the effect algebra, and can be computed using variations on the Kunneth and Mayer-Vietoris sequences. The second way involves a chain complex of ordered abelian groups, and gives rise to a cohomological characterization of state extensions on effect algebras. This has applications to no-go theorems in quantum foundations, such as Bell's theorem.
Shafarevich, Igor Rostislavovich
2005-01-01
This book is wholeheartedly recommended to every student or user of mathematics. Although the author modestly describes his book as 'merely an attempt to talk about' algebra, he succeeds in writing an extremely original and highly informative essay on algebra and its place in modern mathematics and science. From the fields, commutative rings and groups studied in every university math course, through Lie groups and algebras to cohomology and category theory, the author shows how the origins of each algebraic concept can be related to attempts to model phenomena in physics or in other branches
Solomon, Alan D
2012-01-01
REA's Essentials provide quick and easy access to critical information in a variety of different fields, ranging from the most basic to the most advanced. As its name implies, these concise, comprehensive study guides summarize the essentials of the field covered. Essentials are helpful when preparing for exams, doing homework and will remain a lasting reference source for students, teachers, and professionals. Boolean Algebra includes set theory, sentential calculus, fundamental ideas of Boolean algebras, lattices, rings and Boolean algebras, the structure of a Boolean algebra, and Boolean
Kimura, Taro; Pestun, Vasily
2018-06-01
For a quiver with weighted arrows, we define gauge-theory K-theoretic W-algebra generalizing the definition of Shiraishi et al. and Frenkel and Reshetikhin. In particular, we show that the qq-character construction of gauge theory presented by Nekrasov is isomorphic to the definition of the W-algebra in the operator formalism as a commutant of screening charges in the free field representation. Besides, we allow arbitrary quiver and expect interesting applications to representation theory of generalized Borcherds-Kac-Moody Lie algebras, their quantum affinizations and associated W-algebras.
Fast algorithms for transport models. Final report, June 1, 1993--May 31, 1994
International Nuclear Information System (INIS)
Manteuffel, T.
1994-12-01
The focus of this project is the study of multigrid and multilevel algorithms for the numerical solution of Boltzmann models of the transport of neutral and charged particles. In previous work a fast multigrid algorithm was developed for the numerical solution of the Boltzmann model of neutral particle transport in slab geometry assuming isotropic scattering. The new algorithm is extremely fast in the thick diffusion limit; the multigrid v-cycle convergence factor approaches zero as the mean-free-path between collisions approaches zero, independent of the mesh. Also, a fast multilevel method was developed for the numerical solution of the Boltzmann model of charged particle transport in the thick Fokker-Plank limit for slab geometry. Parallel implementations were developed for both algorithms
From Rota-Baxter algebras to pre-Lie algebras
International Nuclear Information System (INIS)
An Huihui; Ba, Chengming
2008-01-01
Rota-Baxter algebras were introduced to solve some analytic and combinatorial problems and have appeared in many fields in mathematics and mathematical physics. Rota-Baxter algebras provide a construction of pre-Lie algebras from associative algebras. In this paper, we give all Rota-Baxter operators of weight 1 on complex associative algebras in dimension ≤3 and their corresponding pre-Lie algebras
Differential Hopf algebra structures on the universal enveloping algebra of a Lie algebra
van den Hijligenberg, N.W.; van den Hijligenberg, N.W.; Martini, Ruud
1995-01-01
We discuss a method to construct a De Rham complex (differential algebra) of Poincar'e-Birkhoff-Witt-type on the universal enveloping algebra of a Lie algebra $g$. We determine the cases in which this gives rise to a differential Hopf algebra that naturally extends the Hopf algebra structure of
Differential Hopf algebra structures on the universal enveloping algebra ofa Lie algebra
N.W. van den Hijligenberg; R. Martini
1995-01-01
textabstractWe discuss a method to construct a De Rham complex (differential algebra) of Poincar'e-Birkhoff-Witt-type on the universal enveloping algebra of a Lie algebra $g$. We determine the cases in which this gives rise to a differential Hopf algebra that naturally extends the Hopf algebra
Algebraic monoids, group embeddings, and algebraic combinatorics
Li, Zhenheng; Steinberg, Benjamin; Wang, Qiang
2014-01-01
This book contains a collection of fifteen articles and is dedicated to the sixtieth birthdays of Lex Renner and Mohan Putcha, the pioneers of the field of algebraic monoids. Topics presented include: v structure and representation theory of reductive algebraic monoids v monoid schemes and applications of monoids v monoids related to Lie theory v equivariant embeddings of algebraic groups v constructions and properties of monoids from algebraic combinatorics v endomorphism monoids induced from vector bundles v Hodge–Newton decompositions of reductive monoids A portion of these articles are designed to serve as a self-contained introduction to these topics, while the remaining contributions are research articles containing previously unpublished results, which are sure to become very influential for future work. Among these, for example, the important recent work of Michel Brion and Lex Renner showing that the algebraic semigroups are strongly π-regular. Graduate students as well a...
Annual Copper Mountain Conferences on Multigrid and Iterative Methods, Copper Mountain, Colorado
International Nuclear Information System (INIS)
McCormick, Stephen F.
2016-01-01
This project supported the Copper Mountain Conference on Multigrid and Iterative Methods, held from 2007 to 2015, at Copper Mountain, Colorado. The subject of the Copper Mountain Conference Series alternated between Multigrid Methods in odd-numbered years and Iterative Methods in even-numbered years. Begun in 1983, the Series represents an important forum for the exchange of ideas in these two closely related fields. This report describes the Copper Mountain Conference on Multigrid and Iterative Methods, 2007-2015. Information on the conference series is available at http://grandmaster.colorado.edu/~copper/
Annual Copper Mountain Conferences on Multigrid and Iterative Methods, Copper Mountain, Colorado
Energy Technology Data Exchange (ETDEWEB)
McCormick, Stephen F. [Front Range Scientific, Inc., Lake City, CO (United States)
2016-03-25
This project supported the Copper Mountain Conference on Multigrid and Iterative Methods, held from 2007 to 2015, at Copper Mountain, Colorado. The subject of the Copper Mountain Conference Series alternated between Multigrid Methods in odd-numbered years and Iterative Methods in even-numbered years. Begun in 1983, the Series represents an important forum for the exchange of ideas in these two closely related fields. This report describes the Copper Mountain Conference on Multigrid and Iterative Methods, 2007-2015. Information on the conference series is available at http://grandmaster.colorado.edu/~copper/.
(Quasi-)Poisson enveloping algebras
Yang, Yan-Hong; Yao, Yuan; Ye, Yu
2010-01-01
We introduce the quasi-Poisson enveloping algebra and Poisson enveloping algebra for a non-commutative Poisson algebra. We prove that for a non-commutative Poisson algebra, the category of quasi-Poisson modules is equivalent to the category of left modules over its quasi-Poisson enveloping algebra, and the category of Poisson modules is equivalent to the category of left modules over its Poisson enveloping algebra.
Levy, Alissa Beth
2012-01-01
The California Department of Education (CDE) has long asserted that success Algebra I by Grade 8 is the goal for all California public school students. In fact, the state's accountability system penalizes schools that do not require all of their students to take the Algebra I end-of-course examination by Grade 8 (CDE, 2009). In this dissertation,…
Learning Activity Package, Algebra.
Evans, Diane
A set of ten teacher-prepared Learning Activity Packages (LAPs) in beginning algebra and nine in intermediate algebra, these units cover sets, properties of operations, number systems, open expressions, solution sets of equations and inequalities in one and two variables, exponents, factoring and polynomials, relations and functions, radicals,…
Herriott, Scott R.; Dunbar, Steven R.
2009-01-01
The common understanding within the mathematics community is that the role of the college algebra course is to prepare students for calculus. Though exceptions are emerging, the curriculum of most college algebra courses and the content of most textbooks on the market both reflect that assumption. This article calls that assumption into question…
Seo, Young Joo; Kim, Young Hee
2016-01-01
In this paper we construct some real algebras by using elementary functions, and discuss some relations between several axioms and its related conditions for such functions. We obtain some conditions for real-valued functions to be a (edge) d -algebra.
Hayden, Dunstan; Cuevas, Gilberto
The pre-algebra lexicon is a set of classroom exercises designed to teach the technical words and phrases of pre-algebra mathematics, and includes the terms most commonly found in related mathematics courses. The lexicon has three parts, each with its own introduction. The first introduces vocabulary items in three groups forming a learning…
Algebraic Description of Motion
Davidon, William C.
1974-01-01
An algebraic definition of time differentiation is presented and used to relate independent measurements of position and velocity. With this, students can grasp certain essential physical, geometric, and algebraic properties of motion and differentiation before undertaking the study of limits. (Author)
Lawson, C. L.; Krogh, F. T.; Gold, S. S.; Kincaid, D. R.; Sullivan, J.; Williams, E.; Hanson, R. J.; Haskell, K.; Dongarra, J.; Moler, C. B.
1982-01-01
The Basic Linear Algebra Subprograms (BLAS) library is a collection of 38 FORTRAN-callable routines for performing basic operations of numerical linear algebra. BLAS library is portable and efficient source of basic operations for designers of programs involving linear algebriac computations. BLAS library is supplied in portable FORTRAN and Assembler code versions for IBM 370, UNIVAC 1100 and CDC 6000 series computers.
Elements of mathematics algebra
Bourbaki, Nicolas
2003-01-01
This is a softcover reprint of the English translation of 1990 of the revised and expanded version of Bourbaki's, Algèbre, Chapters 4 to 7 (1981). This completes Algebra, 1 to 3, by establishing the theories of commutative fields and modules over a principal ideal domain. Chapter 4 deals with polynomials, rational fractions and power series. A section on symmetric tensors and polynomial mappings between modules, and a final one on symmetric functions, have been added. Chapter 5 was entirely rewritten. After the basic theory of extensions (prime fields, algebraic, algebraically closed, radical extension), separable algebraic extensions are investigated, giving way to a section on Galois theory. Galois theory is in turn applied to finite fields and abelian extensions. The chapter then proceeds to the study of general non-algebraic extensions which cannot usually be found in textbooks: p-bases, transcendental extensions, separability criterions, regular extensions. Chapter 6 treats ordered groups and fields and...
Algebraic Side-Channel Attack on Twofish
Directory of Open Access Journals (Sweden)
Chujiao Ma
2017-05-01
Full Text Available While algebraic side-channel attack (ASCA has been successful in breaking simple cryptographic algorithms, it has never been done on larger or more complex algorithms such as Twofish. Compared to other algorithms that ASCA has been used on, Twofish is more difficult to attack due to the key-dependent S-boxes as well as the complex key scheduling. In this paper, we propose the first algebraic side-channel attack on Twofish, and examine the importance of side-channel information in getting past the key-dependent S-boxes and the complex key scheduling. The cryptographic algorithm and side-channel information are both expressed as boolean equations and a SAT solver is used to recover the key. While algebraic attack by itself is not sufficient to break the algorithm, with the help of side-channel information such as Hamming weights, we are able to correctly solve for 96 bits of the 128 bits key in under 2 hours with known plaintext/ciphertext.
Multigrid and defect correction for the steady Navier-Stokes equations : application to aerodynamics
Koren, B.
1991-01-01
Theoretical and expcrimental convergence results are presented for nonlinear multigrid and iterative defect correction applied to finite volume discretizations of the full, steady, 2D, compressible NavierStokes equations. lterative defect correction is introduced for circumventing the difficulty in
Multigrid and defect correction for the steady Navier-Stokes equations
Koren, B.
1990-01-01
Theoretical and experimental convergence results are presented for nonlinear multigrid and iterative defect correction applied to finite volume discretizations of the full, steady, 2D, compressible Navier-Stokes equations. Iterative defect correction is introduced for circumventing the difficulty in
Algebraic theory of locally nilpotent derivations
Freudenburg, Gene
2017-01-01
This book explores the theory and application of locally nilpotent derivations, a subject motivated by questions in affine algebraic geometry and having fundamental connections to areas such as commutative algebra, representation theory, Lie algebras and differential equations. The author provides a unified treatment of the subject, beginning with 16 First Principles on which the theory is based. These are used to establish classical results, such as Rentschler's Theorem for the plane and the Cancellation Theorem for Curves. More recent results, such as Makar-Limanov's theorem for locally nilpotent derivations of polynomial rings, are also discussed. Topics of special interest include progress in classifying additive actions on three-dimensional affine space, finiteness questions (Hilbert's 14th Problem), algorithms, the Makar-Limanov invariant, and connections to the Cancellation Problem and the Embedding Problem. A lot of new material is included in this expanded second edition, such as canonical factoriza...
Cluster algebras bases on vertex operator algebras
Czech Academy of Sciences Publication Activity Database
Zuevsky, Alexander
2016-01-01
Roč. 30, 28-29 (2016), č. článku 1640030. ISSN 0217-9792 Institutional support: RVO:67985840 Keywords : cluster alegbras * vertex operator algebras * Riemann surfaces Subject RIV: BA - General Mathematics Impact factor: 0.736, year: 2016 http://www.worldscientific.com/doi/abs/10.1142/S0217979216400300
Algebraic K-theory and algebraic topology
Energy Technology Data Exchange (ETDEWEB)
Berrick, A J [Department of Mathematics, National University of Singapore (Singapore)
2003-09-15
This contribution treats the various topological constructions of Algebraic K-theory together with the underlying homotopy theory. Topics covered include the plus construction together with its various ramifications and applications, Topological Hochschild and Cyclic Homology as well as K-theory of the ring of integers.
An introduction to algebraic geometry and algebraic groups
Geck, Meinolf
2003-01-01
An accessible text introducing algebraic geometries and algebraic groups at advanced undergraduate and early graduate level, this book develops the language of algebraic geometry from scratch and uses it to set up the theory of affine algebraic groups from first principles.Building on the background material from algebraic geometry and algebraic groups, the text provides an introduction to more advanced and specialised material. An example is the representation theory of finite groups of Lie type.The text covers the conjugacy of Borel subgroups and maximal tori, the theory of algebraic groups
A cluster algorithm for graphs
S. van Dongen
2000-01-01
textabstractA cluster algorithm for graphs called the emph{Markov Cluster algorithm (MCL~algorithm) is introduced. The algorithm provides basically an interface to an algebraic process defined on stochastic matrices, called the MCL~process. The graphs may be both weighted (with nonnegative weight)
Springer, T A
1998-01-01
"[The first] ten chapters...are an efficient, accessible, and self-contained introduction to affine algebraic groups over an algebraically closed field. The author includes exercises and the book is certainly usable by graduate students as a text or for self-study...the author [has a] student-friendly style… [The following] seven chapters... would also be a good introduction to rationality issues for algebraic groups. A number of results from the literature…appear for the first time in a text." –Mathematical Reviews (Review of the Second Edition) "This book is a completely new version of the first edition. The aim of the old book was to present the theory of linear algebraic groups over an algebraically closed field. Reading that book, many people entered the research field of linear algebraic groups. The present book has a wider scope. Its aim is to treat the theory of linear algebraic groups over arbitrary fields. Again, the author keeps the treatment of prerequisites self-contained. The material of t...
Computer methods in general relativity: algebraic computing
Araujo, M E; Skea, J E F; Koutras, A; Krasinski, A; Hobill, D; McLenaghan, R G; Christensen, S M
1993-01-01
Karlhede & MacCallum [1] gave a procedure for determining the Lie algebra of the isometry group of an arbitrary pseudo-Riemannian manifold, which they intended to im- plement using the symbolic manipulation package SHEEP but never did. We have recently ﬁnished making this procedure explicit by giving an algorithm suitable for implemen- tation on a computer [2]. Specifically, we have written an algorithm for determining the isometry group of a spacetime (in four dimensions), and partially implemented this algorithm using the symbolic manipulation package CLASSI, which is an extension of SHEEP.
Solving the Fluid Pressure Poisson Equation Using Multigrid-Evaluation and Improvements.
Dick, Christian; Rogowsky, Marcus; Westermann, Rudiger
2016-11-01
In many numerical simulations of fluids governed by the incompressible Navier-Stokes equations, the pressure Poisson equation needs to be solved to enforce mass conservation. Multigrid solvers show excellent convergence in simple scenarios, yet they can converge slowly in domains where physically separated regions are combined at coarser scales. Moreover, existing multigrid solvers are tailored to specific discretizations of the pressure Poisson equation, and they cannot easily be adapted to other discretizations. In this paper we analyze the convergence properties of existing multigrid solvers for the pressure Poisson equation in different simulation domains, and we show how to further improve the multigrid convergence rate by using a graph-based extension to determine the coarse grid hierarchy. The proposed multigrid solver is generic in that it can be applied to different kinds of discretizations of the pressure Poisson equation, by using solely the specification of the simulation domain and pre-assembled computational stencils. We analyze the proposed solver in combination with finite difference and finite volume discretizations of the pressure Poisson equation. Our evaluations show that, despite the common assumption, multigrid schemes can exploit their potential even in the most complicated simulation scenarios, yet this behavior is obtained at the price of higher memory consumption.
Schneider, Hans
1989-01-01
Linear algebra is one of the central disciplines in mathematics. A student of pure mathematics must know linear algebra if he is to continue with modern algebra or functional analysis. Much of the mathematics now taught to engineers and physicists requires it.This well-known and highly regarded text makes the subject accessible to undergraduates with little mathematical experience. Written mainly for students in physics, engineering, economics, and other fields outside mathematics, the book gives the theory of matrices and applications to systems of linear equations, as well as many related t
Quantitative Algebraic Reasoning
DEFF Research Database (Denmark)
Mardare, Radu Iulian; Panangaden, Prakash; Plotkin, Gordon
2016-01-01
We develop a quantitative analogue of equational reasoning which we call quantitative algebra. We deﬁne an equality relation indexed by rationals: a =ε b which we think of as saying that “a is approximately equal to b up to an error of ε”. We have 4 interesting examples where we have a quantitative...... equational theory whose free algebras correspond to well known structures. In each case we have ﬁnitary and continuous versions. The four cases are: Hausdorﬀ metrics from quantitive semilattices; pWasserstein metrics (hence also the Kantorovich metric) from barycentric algebras and also from pointed...
Chatterjee, D
2007-01-01
About the Book: This book provides exposition of the subject both in its general and algebraic aspects. It deals with the notions of topological spaces, compactness, connectedness, completeness including metrizability and compactification, algebraic aspects of topological spaces through homotopy groups and homology groups. It begins with the basic notions of topological spaces but soon going beyond them reaches the domain of algebra through the notions of homotopy, homology and cohomology. How these approaches work in harmony is the subject matter of this book. The book finally arrives at the
Adaptive algebraic reconstruction technique
International Nuclear Information System (INIS)
Lu Wenkai; Yin Fangfang
2004-01-01
Algebraic reconstruction techniques (ART) are iterative procedures for reconstructing objects from their projections. It is proven that ART can be computationally efficient by carefully arranging the order in which the collected data are accessed during the reconstruction procedure and adaptively adjusting the relaxation parameters. In this paper, an adaptive algebraic reconstruction technique (AART), which adopts the same projection access scheme in multilevel scheme algebraic reconstruction technique (MLS-ART), is proposed. By introducing adaptive adjustment of the relaxation parameters during the reconstruction procedure, one-iteration AART can produce reconstructions with better quality, in comparison with one-iteration MLS-ART. Furthermore, AART outperforms MLS-ART with improved computational efficiency
Cohen, A.M.; Liu, S.
2011-01-01
For each n>0, we define an algebra having many properties that one might expect to hold for a Brauer algebra of type Bn. It is defined by means of a presentation by generators and relations. We show that this algebra is a subalgebra of the Brauer algebra of type Dn+1 and point out a cellular
Profinite algebras and affine boundedness
Schneider, Friedrich Martin; Zumbrägel, Jens
2015-01-01
We prove a characterization of profinite algebras, i.e., topological algebras that are isomorphic to a projective limit of finite discrete algebras. In general profiniteness concerns both the topological and algebraic characteristics of a topological algebra, whereas for topological groups, rings, semigroups, and distributive lattices, profiniteness turns out to be a purely topological property as it is is equivalent to the underlying topological space being a Stone space. Condensing the core...
Pseudo-Riemannian Novikov algebras
Energy Technology Data Exchange (ETDEWEB)
Chen Zhiqi; Zhu Fuhai [School of Mathematical Sciences and LPMC, Nankai University, Tianjin 300071 (China)], E-mail: chenzhiqi@nankai.edu.cn, E-mail: zhufuhai@nankai.edu.cn
2008-08-08
Novikov algebras were introduced in connection with the Poisson brackets of hydrodynamic-type and Hamiltonian operators in formal variational calculus. Pseudo-Riemannian Novikov algebras denote Novikov algebras with non-degenerate invariant symmetric bilinear forms. In this paper, we find that there is a remarkable geometry on pseudo-Riemannian Novikov algebras, and give a special class of pseudo-Riemannian Novikov algebras.
International Nuclear Information System (INIS)
Lebedenko, V.M.
1978-01-01
The PR-algebras, i.e. the Lie algebras with commutation relations of [Hsub(i),Hsub(j)]=rsub(ij)Hsub(i)(i< j) type are investigated. On the basis of former results a criterion for the membership of 2-solvable Lie algebras to the PR-algebra class is given. The conditions imposed by the criterion are formulated in the linear algebra language
Indian Academy of Sciences (India)
algebraic geometry but also in related fields like number theory. ... every vector bundle on the affine space is trivial. (equivalently ... les on a compact Riemann surface to unitary rep- ... tial geometry and topology and was generalised in.
Axler, Sheldon
2015-01-01
This best-selling textbook for a second course in linear algebra is aimed at undergrad math majors and graduate students. The novel approach taken here banishes determinants to the end of the book. The text focuses on the central goal of linear algebra: understanding the structure of linear operators on finite-dimensional vector spaces. The author has taken unusual care to motivate concepts and to simplify proofs. A variety of interesting exercises in each chapter helps students understand and manipulate the objects of linear algebra. The third edition contains major improvements and revisions throughout the book. More than 300 new exercises have been added since the previous edition. Many new examples have been added to illustrate the key ideas of linear algebra. New topics covered in the book include product spaces, quotient spaces, and dual spaces. Beautiful new formatting creates pages with an unusually pleasant appearance in both print and electronic versions. No prerequisites are assumed other than the ...
Algebraic Semantics for Narrative
Kahn, E.
1974-01-01
This paper uses discussion of Edmund Spenser's "The Faerie Queene" to present a theoretical framework for explaining the semantics of narrative discourse. The algebraic theory of finite automata is used. (CK)
Leamer, Micah J.
2004-01-01
Let K be a field and Q a finite directed multi-graph. In this paper I classify all path algebras KQ and admissible orders with the property that all of their finitely generated ideals have finite Groebner bases. MS
Differential Hopf algebra structures on the Universal Enveloping Algebra of a Lie Algebra
van den Hijligenberg, N.W.; van den Hijligenberg, N.; Martini, Ruud
1995-01-01
We discuss a method to construct a De Rham complex (differential algebra) of Poincaré–Birkhoff–Witt type on the universal enveloping algebra of a Lie algebra g. We determine the cases in which this gives rise to a differential Hopf algebra that naturally extends the Hopf algebrastructure of U(g).
International Nuclear Information System (INIS)
Waldron, A.K.; Joshi, G.C.
1992-01-01
By considering representation theory for non-associative algebras the fundamental adjoint representations of the octonion algebra is constructed. It is then shown how these representations by associative matrices allow a consistent octonionic gauge theory to be realized. It was found that non-associativity implies the existence of new terms in the transformation laws of fields and the kinetic term of an octonionic Lagrangian. 13 refs
Institute of Scientific and Technical Information of China (English)
Antonio AIZPURU; Antonio GUTI(E)RREZ-D(A)VILA
2004-01-01
In this paper we will study some families and subalgebras ( ) of ( )(N) that let us characterize the unconditional convergence of series through the weak convergence of subseries ∑i∈A xi, A ∈ ( ).As a consequence, we obtain a new version of the Orlicz-Pettis theorem, for Banach spaces. We also study some relationships between algebraic properties of Boolean algebras and topological properties of the corresponding Stone spaces.
Polynomials in algebraic analysis
Multarzyński, Piotr
2012-01-01
The concept of polynomials in the sense of algebraic analysis, for a single right invertible linear operator, was introduced and studied originally by D. Przeworska-Rolewicz \\cite{DPR}. One of the elegant results corresponding with that notion is a purely algebraic version of the Taylor formula, being a generalization of its usual counterpart, well known for functions of one variable. In quantum calculus there are some specific discrete derivations analyzed, which are right invertible linear ...
Intermediate algebra & analytic geometry
Gondin, William R
1967-01-01
Intermediate Algebra & Analytic Geometry Made Simple focuses on the principles, processes, calculations, and methodologies involved in intermediate algebra and analytic geometry. The publication first offers information on linear equations in two unknowns and variables, functions, and graphs. Discussions focus on graphic interpretations, explicit and implicit functions, first quadrant graphs, variables and functions, determinate and indeterminate systems, independent and dependent equations, and defective and redundant systems. The text then examines quadratic equations in one variable, system
Currents on Grassmann algebras
International Nuclear Information System (INIS)
Coquereaux, R.; Ragoucy, E.
1993-09-01
Currents are defined on a Grassmann algebra Gr(N) with N generators as distributions on its exterior algebra (using the symmetric wedge product). The currents are interpreted in terms of Z 2 -graded Hochschild cohomology and closed currents in terms of cyclic cocycles (they are particular multilinear forms on Gr(N)). An explicit construction of the vector space of closed currents of degree p on Gr(N) is given by using Berezin integration. (authors). 10 refs
Introduction to abstract algebra
Nicholson, W Keith
2012-01-01
Praise for the Third Edition ". . . an expository masterpiece of the highest didactic value that has gained additional attractivity through the various improvements . . ."-Zentralblatt MATH The Fourth Edition of Introduction to Abstract Algebra continues to provide an accessible approach to the basic structures of abstract algebra: groups, rings, and fields. The book's unique presentation helps readers advance to abstract theory by presenting concrete examples of induction, number theory, integers modulo n, and permutations before the abstract structures are defined. Readers can immediately be
Bollhöfer, Matthias; Kressner, Daniel; Mehl, Christian; Stykel, Tatjana
2015-01-01
This edited volume highlights the scientific contributions of Volker Mehrmann, a leading expert in the area of numerical (linear) algebra, matrix theory, differential-algebraic equations and control theory. These mathematical research areas are strongly related and often occur in the same real-world applications. The main areas where such applications emerge are computational engineering and sciences, but increasingly also social sciences and economics. This book also reflects some of Volker Mehrmann's major career stages. Starting out working in the areas of numerical linear algebra (his first full professorship at TU Chemnitz was in "Numerical Algebra," hence the title of the book) and matrix theory, Volker Mehrmann has made significant contributions to these areas ever since. The highlights of these are discussed in Parts I and II of the present book. Often the development of new algorithms in numerical linear algebra is motivated by problems in system and control theory. These and his later major work on ...
The Boolean algebra of Galois algebras
Directory of Open Access Journals (Sweden)
Lianyong Xue
2003-02-01
Full Text Available Let B be a Galois algebra with Galois group G, Jg={bÃ¢ÂˆÂˆB|bx=g(xbÃ¢Â€Â‰for allÃ¢Â€Â‰xÃ¢ÂˆÂˆB} for each gÃ¢ÂˆÂˆG, and BJg=Beg for a central idempotent eg, Ba the Boolean algebra generated by {0,eg|gÃ¢ÂˆÂˆG}, e a nonzero element in Ba, and He={gÃ¢ÂˆÂˆG|eeg=e}. Then, a monomial e is characterized, and the Galois extension Be, generated by e with Galois group He, is investigated.
Real division algebras and other algebras motivated by physics
International Nuclear Information System (INIS)
Benkart, G.; Osborn, J.M.
1981-01-01
In this survey we discuss several general techniques which have been productive in the study of real division algebras, flexible Lie-admissible algebras, and other nonassociative algebras, and we summarize results obtained using these methods. The principal method involved in this work is to view an algebra A as a module for a semisimple Lie algebra of derivations of A and to use representation theory to study products in A. In the case of real division algebras, we also discuss the use of isotopy and the use of a generalized Peirce decomposition. Most of the work summarized here has appeared in more detail in various other papers. The exceptions are results on a class of algebras of dimension 15, motivated by physics, which admit the Lie algebra sl(3) as an algebra of derivations
Algebraic Verification Method for SEREs Properties via Groebner Bases Approaches
Directory of Open Access Journals (Sweden)
Ning Zhou
2013-01-01
Full Text Available This work presents an efficient solution using computer algebra system to perform linear temporal properties verification for synchronous digital systems. The method is essentially based on both Groebner bases approaches and symbolic simulation. A mechanism for constructing canonical polynomial set based symbolic representations for both circuit descriptions and assertions is studied. We then present a complete checking algorithm framework based on these algebraic representations by using Groebner bases. The computational experience result in this work shows that the algebraic approach is a quite competitive checking method and will be a useful supplement to the existent verification methods based on simulation.
Formalized Linear Algebra over Elementary Divisor Rings in Coq
Cano , Guillaume; Cohen , Cyril; Dénès , Maxime; Mörtberg , Anders; Siles , Vincent
2016-01-01
International audience; This paper presents a Coq formalization of linear algebra over elementary divisor rings, that is, rings where every matrix is equivalent to a matrix in Smith normal form. The main results are the formalization that these rings support essential operations of linear algebra, the classification theorem of finitely pre-sented modules over such rings and the uniqueness of the Smith normal form up to multiplication by units. We present formally verified algorithms comput-in...
Special set linear algebra and special set fuzzy linear algebra
Kandasamy, W. B. Vasantha; Smarandache, Florentin; Ilanthenral, K.
2009-01-01
The authors in this book introduce the notion of special set linear algebra and special set fuzzy Linear algebra, which is an extension of the notion set linear algebra and set fuzzy linear algebra. These concepts are best suited in the application of multi expert models and cryptology. This book has five chapters. In chapter one the basic concepts about set linear algebra is given in order to make this book a self contained one. The notion of special set linear algebra and their fuzzy analog...
Hecke algebras with unequal parameters
Lusztig, G
2003-01-01
Hecke algebras arise in representation theory as endomorphism algebras of induced representations. One of the most important classes of Hecke algebras is related to representations of reductive algebraic groups over p-adic or finite fields. In 1979, in the simplest (equal parameter) case of such Hecke algebras, Kazhdan and Lusztig discovered a particular basis (the KL-basis) in a Hecke algebra, which is very important in studying relations between representation theory and geometry of the corresponding flag varieties. It turned out that the elements of the KL-basis also possess very interesting combinatorial properties. In the present book, the author extends the theory of the KL-basis to a more general class of Hecke algebras, the so-called algebras with unequal parameters. In particular, he formulates conjectures describing the properties of Hecke algebras with unequal parameters and presents examples verifying these conjectures in particular cases. Written in the author's precise style, the book gives rese...
Axis Problem of Rough 3-Valued Algebras
Institute of Scientific and Technical Information of China (English)
Jianhua Dai; Weidong Chen; Yunhe Pan
2006-01-01
The collection of all the rough sets of an approximation space has been given several algebraic interpretations, including Stone algebras, regular double Stone algebras, semi-simple Nelson algebras, pre-rough algebras and 3-valued Lukasiewicz algebras. A 3-valued Lukasiewicz algebra is a Stone algebra, a regular double Stone algebra, a semi-simple Nelson algebra, a pre-rough algebra. Thus, we call the algebra constructed by the collection of rough sets of an approximation space a rough 3-valued Lukasiewicz algebra. In this paper,the rough 3-valued Lukasiewicz algebras, which are a special kind of 3-valued Lukasiewicz algebras, are studied. Whether the rough 3-valued Lukasiewicz algebra is a axled 3-valued Lukasiewicz algebra is examined.
Davidson, Kenneth R
1996-01-01
The subject of C*-algebras received a dramatic revitalization in the 1970s by the introduction of topological methods through the work of Brown, Douglas, and Fillmore on extensions of C*-algebras and Elliott's use of K-theory to provide a useful classification of AF algebras. These results were the beginning of a marvelous new set of tools for analyzing concrete C*-algebras. This book is an introductory graduate level text which presents the basics of the subject through a detailed analysis of several important classes of C*-algebras. The development of operator algebras in the last twenty yea
Algebra II workbook for dummies
Sterling, Mary Jane
2014-01-01
To succeed in Algebra II, start practicing now Algebra II builds on your Algebra I skills to prepare you for trigonometry, calculus, and a of myriad STEM topics. Working through practice problems helps students better ingest and retain lesson content, creating a solid foundation to build on for future success. Algebra II Workbook For Dummies, 2nd Edition helps you learn Algebra II by doing Algebra II. Author and math professor Mary Jane Sterling walks you through the entire course, showing you how to approach and solve the problems you encounter in class. You'll begin by refreshing your Algebr
Directory of Open Access Journals (Sweden)
Hans Schonemann
1996-12-01
Full Text Available Some algorithms for singularity theory and algebraic geometry The use of Grobner basis computations for treating systems of polynomial equations has become an important tool in many areas. This paper introduces of the concept of standard bases (a generalization of Grobner bases and the application to some problems from algebraic geometry. The examples are presented as SINGULAR commands. A general introduction to Grobner bases can be found in the textbook [CLO], an introduction to syzygies in [E] and [St1]. SINGULAR is a computer algebra system for computing information about singularities, for use in algebraic geometry. The basic algorithms in SINGULAR are several variants of a general standard basis algorithm for general monomial orderings (see [GG]. This includes wellorderings (Buchberger algorithm ([B1], [B2] and tangent cone orderings (Mora algorithm ([M1], [MPT] as special cases: It is able to work with non-homogeneous and homogeneous input and also to compute in the localization of the polynomial ring in 0. Recent versions include algorithms to factorize polynomials and a factorizing Grobner basis algorithm. For a complete description of SINGULAR see [Si].
Srinivas, V
1996-01-01
Algebraic K-Theory has become an increasingly active area of research. With its connections to algebra, algebraic geometry, topology, and number theory, it has implications for a wide variety of researchers and graduate students in mathematics. The book is based on lectures given at the author's home institution, the Tata Institute in Bombay, and elsewhere. A detailed appendix on topology was provided in the first edition to make the treatment accessible to readers with a limited background in topology. The second edition also includes an appendix on algebraic geometry that contains the required definitions and results needed to understand the core of the book; this makes the book accessible to a wider audience. A central part of the book is a detailed exposition of the ideas of Quillen as contained in his classic papers "Higher Algebraic K-Theory, I, II." A more elementary proof of the theorem of Merkujev--Suslin is given in this edition; this makes the treatment of this topic self-contained. An application ...
Regularity of C*-algebras and central sequence algebras
DEFF Research Database (Denmark)
Christensen, Martin S.
The main topic of this thesis is regularity properties of C*-algebras and how these regularity properties are re ected in their associated central sequence algebras. The thesis consists of an introduction followed by four papers [A], [B], [C], [D]. In [A], we show that for the class of simple...... Villadsen algebra of either the rst type with seed space a nite dimensional CW complex, or the second type, tensorial absorption of the Jiang-Su algebra is characterized by the absence of characters on the central sequence algebra. Additionally, in a joint appendix with Joan Bosa, we show that the Villadsen...... algebra of the second type with innite stable rank fails the corona factorization property. In [B], we consider the class of separable C*-algebras which do not admit characters on their central sequence algebra, and show that it has nice permanence properties. We also introduce a new divisibility property...
Interactions Between Representation Ttheory, Algebraic Topology and Commutative Algebra
Pitsch, Wolfgang; Zarzuela, Santiago
2016-01-01
This book includes 33 expanded abstracts of selected talks given at the two workshops "Homological Bonds Between Commutative Algebra and Representation Theory" and "Brave New Algebra: Opening Perspectives," and the conference "Opening Perspectives in Algebra, Representations, and Topology," held at the Centre de Recerca Matemàtica (CRM) in Barcelona between January and June 2015. These activities were part of the one-semester intensive research program "Interactions Between Representation Theory, Algebraic Topology and Commutative Algebra (IRTATCA)." Most of the abstracts present preliminary versions of not-yet published results and cover a large number of topics (including commutative and non commutative algebra, algebraic topology, singularity theory, triangulated categories, representation theory) overlapping with homological methods. This comprehensive book is a valuable resource for the community of researchers interested in homological algebra in a broad sense, and those curious to learn the latest dev...
Quantum cluster algebra structures on quantum nilpotent algebras
Goodearl, K R
2017-01-01
All algebras in a very large, axiomatically defined class of quantum nilpotent algebras are proved to possess quantum cluster algebra structures under mild conditions. Furthermore, it is shown that these quantum cluster algebras always equal the corresponding upper quantum cluster algebras. Previous approaches to these problems for the construction of (quantum) cluster algebra structures on (quantized) coordinate rings arising in Lie theory were done on a case by case basis relying on the combinatorics of each concrete family. The results of the paper have a broad range of applications to these problems, including the construction of quantum cluster algebra structures on quantum unipotent groups and quantum double Bruhat cells (the Berenstein-Zelevinsky conjecture), and treat these problems from a unified perspective. All such applications also establish equality between the constructed quantum cluster algebras and their upper counterparts.
Identities and derivations for Jacobian algebras
International Nuclear Information System (INIS)
Dzhumadil'daev, A.S.
2001-09-01
Constructions of n-Lie algebras by strong n-Lie-Poisson algebras are given. First cohomology groups of adjoint module of Jacobian algebras are calculated. Minimal identities of 3-Jacobian algebra are found. (author)
Algebraic quantum field theory
International Nuclear Information System (INIS)
Foroutan, A.
1996-12-01
The basic assumption that the complete information relevant for a relativistic, local quantum theory is contained in the net structure of the local observables of this theory results first of all in a concise formulation of the algebraic structure of the superselection theory and an intrinsic formulation of charge composition, charge conjugation and the statistics of an algebraic quantum field theory. In a next step, the locality of massive particles together with their spectral properties are wed for the formulation of a selection criterion which opens the access to the massive, non-abelian quantum gauge theories. The role of the electric charge as a superselection rule results in the introduction of charge classes which in term lead to a set of quantum states with optimum localization properties. Finally, the asymptotic observables of quantum electrodynamics are investigated within the framework of algebraic quantum field theory. (author)
Kollár, János
1997-01-01
This volume contains the lectures presented at the third Regional Geometry Institute at Park City in 1993. The lectures provide an introduction to the subject, complex algebraic geometry, making the book suitable as a text for second- and third-year graduate students. The book deals with topics in algebraic geometry where one can reach the level of current research while starting with the basics. Topics covered include the theory of surfaces from the viewpoint of recent higher-dimensional developments, providing an excellent introduction to more advanced topics such as the minimal model program. Also included is an introduction to Hodge theory and intersection homology based on the simple topological ideas of Lefschetz and an overview of the recent interactions between algebraic geometry and theoretical physics, which involve mirror symmetry and string theory.
Launey, Warwick De
2011-01-01
Combinatorial design theory is a source of simply stated, concrete, yet difficult discrete problems, with the Hadamard conjecture being a prime example. It has become clear that many of these problems are essentially algebraic in nature. This book provides a unified vision of the algebraic themes which have developed so far in design theory. These include the applications in design theory of matrix algebra, the automorphism group and its regular subgroups, the composition of smaller designs to make larger designs, and the connection between designs with regular group actions and solutions to group ring equations. Everything is explained at an elementary level in terms of orthogonality sets and pairwise combinatorial designs--new and simple combinatorial notions which cover many of the commonly studied designs. Particular attention is paid to how the main themes apply in the important new context of cocyclic development. Indeed, this book contains a comprehensive account of cocyclic Hadamard matrices. The book...
Peternell, Thomas; Schneider, Michael; Schreyer, Frank-Olaf
1992-01-01
The Bayreuth meeting on "Complex Algebraic Varieties" focussed on the classification of algebraic varieties and topics such as vector bundles, Hodge theory and hermitian differential geometry. Most of the articles in this volume are closely related to talks given at the conference: all are original, fully refereed research articles. CONTENTS: A. Beauville: Annulation du H(1) pour les fibres en droites plats.- M. Beltrametti, A.J. Sommese, J.A. Wisniewski: Results on varieties with many lines and their applications to adjunction theory.- G. Bohnhorst, H. Spindler: The stability of certain vector bundles on P(n) .- F. Catanese, F. Tovena: Vector bundles, linear systems and extensions of (1).- O. Debarre: Vers uns stratification de l'espace des modules des varietes abeliennes principalement polarisees.- J.P. Demailly: Singular hermitian metrics on positive line bundles.- T. Fujita: On adjoint bundles of ample vector bundles.- Y. Kawamata: Moderate degenerations of algebraic surfaces.- U. Persson: Genus two fibra...
Wadsworth, A R
2017-01-01
This is a book of problems in abstract algebra for strong undergraduates or beginning graduate students. It can be used as a supplement to a course or for self-study. The book provides more variety and more challenging problems than are found in most algebra textbooks. It is intended for students wanting to enrich their learning of mathematics by tackling problems that take some thought and effort to solve. The book contains problems on groups (including the Sylow Theorems, solvable groups, presentation of groups by generators and relations, and structure and duality for finite abelian groups); rings (including basic ideal theory and factorization in integral domains and Gauss's Theorem); linear algebra (emphasizing linear transformations, including canonical forms); and fields (including Galois theory). Hints to many problems are also included.
Bloch, Spencer J
2000-01-01
This book is the long-awaited publication of the famous Irvine lectures. Delivered in 1978 at the University of California at Irvine, these lectures turned out to be an entry point to several intimately-connected new branches of arithmetic algebraic geometry, such as regulators and special values of L-functions of algebraic varieties, explicit formulas for them in terms of polylogarithms, the theory of algebraic cycles, and eventually the general theory of mixed motives which unifies and underlies all of the above (and much more). In the 20 years since, the importance of Bloch's lectures has not diminished. A lucky group of people working in the above areas had the good fortune to possess a copy of old typewritten notes of these lectures. Now everyone can have their own copy of this classic work.
Olver, Peter J
2018-01-01
This textbook develops the essential tools of linear algebra, with the goal of imparting technique alongside contextual understanding. Applications go hand-in-hand with theory, each reinforcing and explaining the other. This approach encourages students to develop not only the technical proficiency needed to go on to further study, but an appreciation for when, why, and how the tools of linear algebra can be used across modern applied mathematics. Providing an extensive treatment of essential topics such as Gaussian elimination, inner products and norms, and eigenvalues and singular values, this text can be used for an in-depth first course, or an application-driven second course in linear algebra. In this second edition, applications have been updated and expanded to include numerical methods, dynamical systems, data analysis, and signal processing, while the pedagogical flow of the core material has been improved. Throughout, the text emphasizes the conceptual connections between each application and the un...
Blyth, T S
2002-01-01
Basic Linear Algebra is a text for first year students leading from concrete examples to abstract theorems, via tutorial-type exercises. More exercises (of the kind a student may expect in examination papers) are grouped at the end of each section. The book covers the most important basics of any first course on linear algebra, explaining the algebra of matrices with applications to analytic geometry, systems of linear equations, difference equations and complex numbers. Linear equations are treated via Hermite normal forms which provides a successful and concrete explanation of the notion of linear independence. Another important highlight is the connection between linear mappings and matrices leading to the change of basis theorem which opens the door to the notion of similarity. This new and revised edition features additional exercises and coverage of Cramer's rule (omitted from the first edition). However, it is the new, extra chapter on computer assistance that will be of particular interest to readers:...
Deo, Satya
2018-01-01
This book presents the first concepts of the topics in algebraic topology such as the general simplicial complexes, simplicial homology theory, fundamental groups, covering spaces and singular homology theory in greater detail. Originally published in 2003, this book has become one of the seminal books. Now, in the completely revised and enlarged edition, the book discusses the rapidly developing field of algebraic topology. Targeted to undergraduate and graduate students of mathematics, the prerequisite for this book is minimal knowledge of linear algebra, group theory and topological spaces. The book discusses about the relevant concepts and ideas in a very lucid manner, providing suitable motivations and illustrations. All relevant topics are covered, including the classical theorems like the Brouwer’s fixed point theorem, Lefschetz fixed point theorem, Borsuk-Ulam theorem, Brouwer’s separation theorem and the theorem on invariance of the domain. Most of the exercises are elementary, but sometimes chal...
Abstract Algebra for Algebra Teaching: Influencing School Mathematics Instruction
Wasserman, Nicholas H.
2016-01-01
This article explores the potential for aspects of abstract algebra to be influential for the teaching of school algebra (and early algebra). Using national standards for analysis, four primary areas common in school mathematics--and their progression across elementary, middle, and secondary mathematics--where teaching may be transformed by…
Converting nested algebra expressions into flat algebra expressions
Paredaens, J.; Van Gucht, D.
1992-01-01
Nested relations generalize ordinary flat relations by allowing tuple values to be either atomic or set valued. The nested algebra is a generalization of the flat relational algebra to manipulate nested relations. In this paper we study the expressive power of the nested algebra relative to its
Numerical linear algebra a concise introduction with Matlab and Julia
Bornemann, Folkmar
2018-01-01
This book offers an introduction to the algorithmic-numerical thinking using basic problems of linear algebra. By focusing on linear algebra, it ensures a stronger thematic coherence than is otherwise found in introductory lectures on numerics. The book highlights the usefulness of matrix partitioning compared to a component view, leading not only to a clearer notation and shorter algorithms, but also to significant runtime gains in modern computer architectures. The algorithms and accompanying numerical examples are given in the programming environment MATLAB, and additionally – in an appendix – in the future-oriented, freely accessible programming language Julia. This book is suitable for a two-hour lecture on numerical linear algebra from the second semester of a bachelor's degree in mathematics.
On Associative Conformal Algebras of Linear Growth
Retakh, Alexander
2000-01-01
Lie conformal algebras appear in the theory of vertex algebras. Their relation is similar to that of Lie algebras and their universal enveloping algebras. Associative conformal algebras play a role in conformal representation theory. We introduce the notions of conformal identity and unital associative conformal algebras and classify finitely generated simple unital associative conformal algebras of linear growth. These are precisely the complete algebras of conformal endomorphisms of finite ...
Computer Program For Linear Algebra
Krogh, F. T.; Hanson, R. J.
1987-01-01
Collection of routines provided for basic vector operations. Basic Linear Algebra Subprogram (BLAS) library is collection from FORTRAN-callable routines for employing standard techniques to perform basic operations of numerical linear algebra.
Algebra for Gifted Third Graders.
Borenson, Henry
1987-01-01
Elementary school children who are exposed to a concrete, hands-on experience in algebraic linear equations will more readily develop a positive mind-set and expectation for success in later formal, algebraic studies. (CB)
Gradings on simple Lie algebras
Elduque, Alberto
2013-01-01
Gradings are ubiquitous in the theory of Lie algebras, from the root space decomposition of a complex semisimple Lie algebra relative to a Cartan subalgebra to the beautiful Dempwolff decomposition of E_8 as a direct sum of thirty-one Cartan subalgebras. This monograph is a self-contained exposition of the classification of gradings by arbitrary groups on classical simple Lie algebras over algebraically closed fields of characteristic not equal to 2 as well as on some nonclassical simple Lie algebras in positive characteristic. Other important algebras also enter the stage: matrix algebras, the octonions, and the Albert algebra. Most of the presented results are recent and have not yet appeared in book form. This work can be used as a textbook for graduate students or as a reference for researchers in Lie theory and neighboring areas.
Tensor spaces and exterior algebra
Yokonuma, Takeo
1992-01-01
This book explains, as clearly as possible, tensors and such related topics as tensor products of vector spaces, tensor algebras, and exterior algebras. You will appreciate Yokonuma's lucid and methodical treatment of the subject. This book is useful in undergraduate and graduate courses in multilinear algebra. Tensor Spaces and Exterior Algebra begins with basic notions associated with tensors. To facilitate understanding of the definitions, Yokonuma often presents two or more different ways of describing one object. Next, the properties and applications of tensors are developed, including the classical definition of tensors and the description of relative tensors. Also discussed are the algebraic foundations of tensor calculus and applications of exterior algebra to determinants and to geometry. This book closes with an examination of algebraic systems with bilinear multiplication. In particular, Yokonuma discusses the theory of replicas of Chevalley and several properties of Lie algebras deduced from them.
Dynamical systems and linear algebra
Colonius, Fritz (Prof.)
2007-01-01
Dynamical systems and linear algebra / F. Colonius, W. Kliemann. - In: Handbook of linear algebra / ed. by Leslie Hogben. - Boca Raton : Chapman & Hall/CRC, 2007. - S. 56,1-56,22. - (Discrete mathematics and its applications)
Projector bases and algebraic spinors
International Nuclear Information System (INIS)
Bergdolt, G.
1988-01-01
In the case of complex Clifford algebras a basis is constructed whose elements satisfy projector relations. The relations are sufficient conditions for the elements to span minimal ideals and hence to define algebraic spinors
Contractions of quantum algebraic structures
International Nuclear Information System (INIS)
Doikou, A.; Sfetsos, K.
2010-01-01
A general framework for obtaining certain types of contracted and centrally extended algebras is reviewed. The whole process relies on the existence of quadratic algebras, which appear in the context of boundary integrable models. (Abstract Copyright [2010], Wiley Periodicals, Inc.)
Polynomial Heisenberg algebras
International Nuclear Information System (INIS)
Carballo, Juan M; C, David J Fernandez; Negro, Javier; Nieto, Luis M
2004-01-01
Polynomial deformations of the Heisenberg algebra are studied in detail. Some of their natural realizations are given by the higher order susy partners (and not only by those of first order, as is already known) of the harmonic oscillator for even-order polynomials. Here, it is shown that the susy partners of the radial oscillator play a similar role when the order of the polynomial is odd. Moreover, it will be proved that the general systems ruled by such kinds of algebras, in the quadratic and cubic cases, involve Painleve transcendents of types IV and V, respectively
Classical algebraic chromodynamics
International Nuclear Information System (INIS)
Adler, S.L.
1978-01-01
I develop an extension of the usual equations of SU(n) chromodynamics which permits the consistent introduction of classical, noncommuting quark source charges. The extension involves adding a singlet gluon, giving a U(n) -based theory with outer product P/sup a/(u,v) = (1/2)(d/sup a/bc + if/sup a/bc)(u/sup b/v/sup c/ - v/sup b/u/sup c/) which obeys the Jacobi identity, inner product S (u,v) = (1/2)(u/sup a/v/sup a/ + v/sup a/u/sup a/), and with the n 2 gluon fields elevated to algebraic fields over the quark color charge C* algebra. I show that provided the color charge algebra satisfies the condition S (P (u,v),w) = S (u,P (v,w)) for all elements u,v,w of the algebra, all the standard derivations of Lagrangian chromodynamics continue to hold in the algebraic chromodynamics case. I analyze in detail the color charge algebra in the two-particle (qq, qq-bar, q-barq-bar) case and show that the above consistency condition is satisfied for the following unique (and, interestingly, asymmetric) choice of quark and antiquark charges: Q/sup a//sub q/ = xi/sup a/, Q/sup a//sub q/ = xi-bar/sup a/ + delta/sup a/0(n/2)/sup 3/2/1, with xi/sup a/xi/sup b/ = (1/2)(d/sup a/bc + if/sup a/bc) xi/sup c/, xi-bar/sup a/xi-bar/sup b/ = -(1/2)(d/sup a/bc - if/sup a/bc) xi-bar/sup c/. The algebraic structure of the two-particle U(n) force problem, when expressed on an appropriately diagonalized basis, leads for all n to a classical dynamics problem involving an ordinary SU(2) Yang-Mills field with uniquely specified classical source charges which are nonparallel in the color-singlet state. An explicit calculation shows that local algebraic U(n) gauge transformations lead only to a rigid global rotation of axes in the overlying classical SU(2) problem, which implies that the relative orientations of the classical source charges have physical significance
Weiss, Edwin
1998-01-01
Careful organization and clear, detailed proofs characterize this methodical, self-contained exposition of basic results of classical algebraic number theory from a relatively modem point of view. This volume presents most of the number-theoretic prerequisites for a study of either class field theory (as formulated by Artin and Tate) or the contemporary treatment of analytical questions (as found, for example, in Tate's thesis).Although concerned exclusively with algebraic number fields, this treatment features axiomatic formulations with a considerable range of applications. Modem abstract te
Partially ordered algebraic systems
Fuchs, Laszlo
2011-01-01
Originally published in an important series of books on pure and applied mathematics, this monograph by a distinguished mathematician explores a high-level area in algebra. It constitutes the first systematic summary of research concerning partially ordered groups, semigroups, rings, and fields. The self-contained treatment features numerous problems, complete proofs, a detailed bibliography, and indexes. It presumes some knowledge of abstract algebra, providing necessary background and references where appropriate. This inexpensive edition of a hard-to-find systematic survey will fill a gap i
Hohn, Franz E
2012-01-01
This complete and coherent exposition, complemented by numerous illustrative examples, offers readers a text that can teach by itself. Fully rigorous in its treatment, it offers a mathematically sound sequencing of topics. The work starts with the most basic laws of matrix algebra and progresses to the sweep-out process for obtaining the complete solution of any given system of linear equations - homogeneous or nonhomogeneous - and the role of matrix algebra in the presentation of useful geometric ideas, techniques, and terminology.Other subjects include the complete treatment of the structur
Principles of algebraic geometry
Griffiths, Phillip A
1994-01-01
A comprehensive, self-contained treatment presenting general results of the theory. Establishes a geometric intuition and a working facility with specific geometric practices. Emphasizes applications through the study of interesting examples and the development of computational tools. Coverage ranges from analytic to geometric. Treats basic techniques and results of complex manifold theory, focusing on results applicable to projective varieties, and includes discussion of the theory of Riemann surfaces and algebraic curves, algebraic surfaces and the quadric line complex as well as special top
Energy Technology Data Exchange (ETDEWEB)
Christian, J M; McDonald, G S [Joule Physics Laboratory, School of Computing, Science and Engineering, Materials and Physics Research Centre, University of Salford, Salford M5 4WT (United Kingdom); Chamorro-Posada, P, E-mail: j.christian@salford.ac.u [Departamento de Teoria de la Senal y Comunicaciones e Ingenieria Telematica, Universidad de Valladolid, ETSI Telecomunicacion, Campus Miguel Delibes s/n, 47011 Valladolid (Spain)
2010-02-26
We report, to the best of our knowledge, the first exact analytical algebraic solitons of a generalized cubic-quintic Helmholtz equation. This class of governing equation plays a key role in photonics modelling, allowing a full description of the propagation and interaction of broad scalar beams. New conservation laws are presented, and the recovery of paraxial results is discussed in detail. The stability properties of the new solitons are investigated by combining semi-analytical methods and computer simulations. In particular, new general stability regimes are reported for algebraic bright solitons.
Endomorphisms of graph algebras
DEFF Research Database (Denmark)
Conti, Roberto; Hong, Jeong Hee; Szymanski, Wojciech
2012-01-01
We initiate a systematic investigation of endomorphisms of graph C*-algebras C*(E), extending several known results on endomorphisms of the Cuntz algebras O_n. Most but not all of this study is focused on endomorphisms which permute the vertex projections and globally preserve the diagonal MASA D...... that the restriction to the diagonal MASA of an automorphism which globally preserves both D_E and the core AF-subalgebra eventually commutes with the corresponding one-sided shift. Secondly, we exhibit several properties of proper endomorphisms, investigate invertibility of localized endomorphisms both on C...
Kendig, Keith
2015-01-01
Designed to make learning introductory algebraic geometry as easy as possible, this text is intended for advanced undergraduates and graduate students who have taken a one-year course in algebra and are familiar with complex analysis. This newly updated second edition enhances the original treatment's extensive use of concrete examples and exercises with numerous figures that have been specially redrawn in Adobe Illustrator. An introductory chapter that focuses on examples of curves is followed by a more rigorous and careful look at plane curves. Subsequent chapters explore commutative ring th
International Nuclear Information System (INIS)
Christian, J M; McDonald, G S; Chamorro-Posada, P
2010-01-01
We report, to the best of our knowledge, the first exact analytical algebraic solitons of a generalized cubic-quintic Helmholtz equation. This class of governing equation plays a key role in photonics modelling, allowing a full description of the propagation and interaction of broad scalar beams. New conservation laws are presented, and the recovery of paraxial results is discussed in detail. The stability properties of the new solitons are investigated by combining semi-analytical methods and computer simulations. In particular, new general stability regimes are reported for algebraic bright solitons.
Hogben, Leslie
2013-01-01
With a substantial amount of new material, the Handbook of Linear Algebra, Second Edition provides comprehensive coverage of linear algebra concepts, applications, and computational software packages in an easy-to-use format. It guides you from the very elementary aspects of the subject to the frontiers of current research. Along with revisions and updates throughout, the second edition of this bestseller includes 20 new chapters.New to the Second EditionSeparate chapters on Schur complements, additional types of canonical forms, tensors, matrix polynomials, matrix equations, special types of
Algebra & trigonometry I essentials
REA, Editors of
2012-01-01
REA's Essentials provide quick and easy access to critical information in a variety of different fields, ranging from the most basic to the most advanced. As its name implies, these concise, comprehensive study guides summarize the essentials of the field covered. Essentials are helpful when preparing for exams, doing homework and will remain a lasting reference source for students, teachers, and professionals. Algebra & Trigonometry I includes sets and set operations, number systems and fundamental algebraic laws and operations, exponents and radicals, polynomials and rational expressions, eq
Algebra & trigonometry super review
2012-01-01
Get all you need to know with Super Reviews! Each Super Review is packed with in-depth, student-friendly topic reviews that fully explain everything about the subject. The Algebra and Trigonometry Super Review includes sets and set operations, number systems and fundamental algebraic laws and operations, exponents and radicals, polynomials and rational expressions, equations, linear equations and systems of linear equations, inequalities, relations and functions, quadratic equations, equations of higher order, ratios, proportions, and variations. Take the Super Review quizzes to see how much y
Linear Algebra Thoroughly Explained
Vujičić, Milan
2008-01-01
Linear Algebra Thoroughly Explained provides a comprehensive introduction to the subject suitable for adoption as a self-contained text for courses at undergraduate and postgraduate level. The clear and comprehensive presentation of the basic theory is illustrated throughout with an abundance of worked examples. The book is written for teachers and students of linear algebra at all levels and across mathematics and the applied sciences, particularly physics and engineering. It will also be an invaluable addition to research libraries as a comprehensive resource book for the subject.
Introduction to vertex algebras, Borcherds algebras and the Monster Lie algebras
International Nuclear Information System (INIS)
Gebert, R.W.
1993-09-01
The theory of vertex algebras constitutes a mathematically rigorous axiomatic formulation of the algebraic origins of conformal field theory. In this context Borcherds algebras arise as certain ''physical'' subspaces of vertex algebras. The aim of this review is to give a pedagogical introduction into this rapidly-developing area of mathematics. Based on the machinery of formal calculus we present the axiomatic definition of vertex algebras. We discuss the connection with conformal field theory by deriving important implications of these axioms. In particular, many explicit calculations are presented to stress the eminent role of the Jacobi identity axiom for vertex algebras. As a class of concrete examples the vertex algebras associated with even lattices are constructed and it is shown in detail how affine Lie algebras and the fake Monster Lie algebra naturally appear. This leads us to the abstract definition of Borcherds algebras as generalized Kac-Moody algebras and their basic properties. Finally, the results about the simplest generic Borcherds algebras are analysed from the point of view of symmetry in quantum theory and the construction of the Monster Lie algebra is sketched. (orig.)
The theory of algebraic numbers
Pollard, Harry
1998-01-01
An excellent introduction to the basics of algebraic number theory, this concise, well-written volume examines Gaussian primes; polynomials over a field; algebraic number fields; and algebraic integers and integral bases. After establishing a firm introductory foundation, the text explores the uses of arithmetic in algebraic number fields; the fundamental theorem of ideal theory and its consequences; ideal classes and class numbers; and the Fermat conjecture. 1975 edition. References. List of Symbols. Index.
Spin-4 extended conformal algebras
International Nuclear Information System (INIS)
Kakas, A.C.
1988-01-01
We construct spin-4 extended conformal algebras using the second hamiltonian structure of the KdV hierarchy. In the presence of a U(1) current a family of spin-4 algebras exists but the additional requirement that the spin-1 and spin-4 currents commute fixes the algebra uniquely. (orig.)
An algebra of reversible computation.
Wang, Yong
2016-01-01
We design an axiomatization for reversible computation called reversible ACP (RACP). It has four extendible modules: basic reversible processes algebra, algebra of reversible communicating processes, recursion and abstraction. Just like process algebra ACP in classical computing, RACP can be treated as an axiomatization foundation for reversible computation.
Thomys, Janus; Zhang, Xiaohong
2013-01-01
We describe weak-BCC-algebras (also called BZ-algebras) in which the condition (x∗y)∗z = (x∗z)∗y is satisfied only in the case when elements x, y belong to the same branch. We also characterize ideals, nilradicals, and nilpotent elements of such algebras. PMID:24311983
Assessing Elementary Algebra with STACK
Sangwin, Christopher J.
2007-01-01
This paper concerns computer aided assessment (CAA) of mathematics in which a computer algebra system (CAS) is used to help assess students' responses to elementary algebra questions. Using a methodology of documentary analysis, we examine what is taught in elementary algebra. The STACK CAA system, http://www.stack.bham.ac.uk/, which uses the CAS…
Process Algebra and Markov Chains
Brinksma, Hendrik; Hermanns, H.; Brinksma, Hendrik; Hermanns, H.; Katoen, Joost P.
This paper surveys and relates the basic concepts of process algebra and the modelling of continuous time Markov chains. It provides basic introductions to both fields, where we also study the Markov chains from an algebraic perspective, viz. that of Markov chain algebra. We then proceed to study
Process algebra and Markov chains
Brinksma, E.; Hermanns, H.; Brinksma, E.; Hermanns, H.; Katoen, J.P.
2001-01-01
This paper surveys and relates the basic concepts of process algebra and the modelling of continuous time Markov chains. It provides basic introductions to both fields, where we also study the Markov chains from an algebraic perspective, viz. that of Markov chain algebra. We then proceed to study
Algebraic Methods to Design Signals
2015-08-27
to date on designing signals using algebraic and combinatorial methods. Mathematical tools from algebraic number theory, representation theory and... combinatorial objects in designing signals for communication purposes. Sequences and arrays with desirable autocorrelation properties have many...multiple access methods in mobile radio communication systems. We continue our mathematical framework based on group algebras, character theory
Directory of Open Access Journals (Sweden)
Eun Seok Lee
2003-01-01
Full Text Available An axial turbine rotor cascade-shape optimization with unsteady passing wakes was performed to obtain an improved aerodynamic performance using an unsteady flow, Reynolds-averaged Navier-Stokes equations solver that was based on explicit, finite difference; Runge-Kutta multistage time marching; and the diagonalized alternating direction implicit scheme. The code utilized Baldwin-Lomax algebraic and k-ε turbulence modeling. The full approximation storage multigrid method and preconditioning were implemented as iterative convergence-acceleration techniques. An implicit dual-time stepping method was incorporated in order to simulate the unsteady flow fields. The objective function was defined as minimization of total pressure loss and maximization of lift, while the mass flow rate was fixed during the optimization. The design variables were several geometric parameters characterizing airfoil leading edge, camber, stagger angle, and inter-row spacing. The genetic algorithm was used as an optimizer, and the penalty method was introduced for combining the constraints with the objective function. Each individual's objective function was computed simultaneously by using a 32-processor distributedmemory computer. The optimization results indicated that only minor improvements are possible in unsteady rotor/stator aerodynamics by varying these geometric parameters.
Reachability for Finite-State Process Algebras Using Static Analysis
DEFF Research Database (Denmark)
Skrypnyuk, Nataliya; Nielson, Flemming
2011-01-01
of the Data Flow Analysis are used in order to “cut off” some of the branches in the reachability analysis that are not important for determining, whether or not a state is reachable. In this way, it is possible for our reachability algorithm to avoid building large parts of the system altogether and still......In this work we present an algorithm for solving the reachability problem in finite systems that are modelled with process algebras. Our method uses Static Analysis, in particular, Data Flow Analysis, of the syntax of a process algebraic system with multi-way synchronisation. The results...... solve the reachability problem in a precise way....
Bergstra, J.A.; Middelburg, C.A.
2015-01-01
We add probabilistic features to basic thread algebra and its extensions with thread-service interaction and strategic interleaving. Here, threads represent the behaviours produced by instruction sequences under execution and services represent the behaviours exhibited by the components of execution
Indian Academy of Sciences (India)
BOOK REVIEW ... To the Indian reader, the word discourse, evokes a respected ... I dug a bit deeper with Google trans- late, and ... published in a journal of mathematics educa- tion. ... The article on Shafarevich's work elsewhere ... goal then, is to develop the basics of algebra in ... ometric Greeks, and works like a magician.
Thinking Visually about Algebra
Baroudi, Ziad
2015-01-01
Many introductions to algebra in high school begin with teaching students to generalise linear numerical patterns. This article argues that this approach needs to be changed so that students encounter variables in the context of modelling visual patterns so that the variables have a meaning. The article presents sample classroom activities,…
The algebraic collective model
International Nuclear Information System (INIS)
Rowe, D.J.; Turner, P.S.
2005-01-01
A recently proposed computationally tractable version of the Bohr collective model is developed to the extent that we are now justified in describing it as an algebraic collective model. The model has an SU(1,1)xSO(5) algebraic structure and a continuous set of exactly solvable limits. Moreover, it provides bases for mixed symmetry collective model calculations. However, unlike the standard realization of SU(1,1), used for computing beta wave functions and their matrix elements in a spherical basis, the algebraic collective model makes use of an SU(1,1) algebra that generates wave functions appropriate for deformed nuclei with intrinsic quadrupole moments ranging from zero to any large value. A previous paper focused on the SO(5) wave functions, as SO(5) (hyper-)spherical harmonics, and computation of their matrix elements. This paper gives analytical expressions for the beta matrix elements needed in applications of the model and illustrative results to show the remarkable gain in efficiency that is achieved by using such a basis in collective model calculations for deformed nuclei
Benjamin, Carl; And Others
Presented are student performance objectives, a student progress chart, and assignment sheets with objective and diagnostic measures for the stated performance objectives in College Algebra I. Topics covered include: sets; vocabulary; linear equations; inequalities; real numbers; operations; factoring; fractions; formulas; ratio, proportion, and…
Swan, R G
1968-01-01
From the Introduction: "These notes are taken from a course on algebraic K-theory [given] at the University of Chicago in 1967. They also include some material from an earlier course on abelian categories, elaborating certain parts of Gabriel's thesis. The results on K-theory are mostly of a very general nature."
Bergstra, J.A.; Baeten, J.C.M.
1993-01-01
The real time process algebra of Baeten and Bergstra [Formal Aspects of Computing, 3, 142-188 (1991)] is extended to real space by requiring the presence of spatial coordinates for each atomic action, in addition to the required temporal attribute. It is found that asynchronous communication
Commutative algebra with a view toward algebraic geometry
Eisenbud, David
1995-01-01
Commutative Algebra is best understood with knowledge of the geometric ideas that have played a great role in its formation, in short, with a view towards algebraic geometry. The author presents a comprehensive view of commutative algebra, from basics, such as localization and primary decomposition, through dimension theory, differentials, homological methods, free resolutions and duality, emphasizing the origins of the ideas and their connections with other parts of mathematics. Many exercises illustrate and sharpen the theory and extended exercises give the reader an active part in complementing the material presented in the text. One novel feature is a chapter devoted to a quick but thorough treatment of Grobner basis theory and the constructive methods in commutative algebra and algebraic geometry that flow from it. Applications of the theory and even suggestions for computer algebra projects are included. This book will appeal to readers from beginners to advanced students of commutative algebra or algeb...
Multi-grid Particle-in-cell Simulations of Plasma Microturbulence
International Nuclear Information System (INIS)
Lewandowski, J.L.V.
2003-01-01
A new scheme to accurately retain kinetic electron effects in particle-in-cell (PIC) simulations for the case of electrostatic drift waves is presented. The splitting scheme, which is based on exact separation between adiabatic and on adiabatic electron responses, is shown to yield more accurate linear growth rates than the standard df scheme. The linear and nonlinear elliptic problems that arise in the splitting scheme are solved using a multi-grid solver. The multi-grid particle-in-cell approach offers an attractive path, both from the physics and numerical points of view, to simulate kinetic electron dynamics in global toroidal plasmas
A Cost-Effective Smoothed Multigrid with Modified Neighborhood-Based Aggregation for Markov Chains
Directory of Open Access Journals (Sweden)
Zhao-Li Shen
2015-01-01
Full Text Available Smoothed aggregation multigrid method is considered for computing stationary distributions of Markov chains. A judgement which determines whether to implement the whole aggregation procedure is proposed. Through this strategy, a large amount of time in the aggregation procedure is saved without affecting the convergence behavior. Besides this, we explain the shortage and irrationality of the Neighborhood-Based aggregation which is commonly used in multigrid methods. Then a modified version is presented to remedy and improve it. Numerical experiments on some typical Markov chain problems are reported to illustrate the performance of these methods.
Multigrid for the Galerkin least squares method in linear elasticity: The pure displacement problem
Energy Technology Data Exchange (ETDEWEB)
Yoo, Jaechil [Univ. of Wisconsin, Madison, WI (United States)
1996-12-31
Franca and Stenberg developed several Galerkin least squares methods for the solution of the problem of linear elasticity. That work concerned itself only with the error estimates of the method. It did not address the related problem of finding effective methods for the solution of the associated linear systems. In this work, we prove the convergence of a multigrid (W-cycle) method. This multigrid is robust in that the convergence is uniform as the parameter, v, goes to 1/2 Computational experiments are included.
Operator algebras and topology
International Nuclear Information System (INIS)
Schick, T.
2002-01-01
These notes, based on three lectures on operator algebras and topology at the 'School on High Dimensional Manifold Theory' at the ICTP in Trieste, introduce a new set of tools to high dimensional manifold theory, namely techniques coming from the theory of operator algebras, in particular C*-algebras. These are extensively studied in their own right. We will focus on the basic definitions and properties, and on their relevance to the geometry and topology of manifolds. A central pillar of work in the theory of C*-algebras is the Baum-Connes conjecture. This is an isomorphism conjecture, as discussed in the talks of Luck, but with a certain special flavor. Nevertheless, it has important direct applications to the topology of manifolds, it implies e.g. the Novikov conjecture. In the first chapter, the Baum-Connes conjecture will be explained and put into our context. Another application of the Baum-Connes conjecture is to the positive scalar curvature question. This will be discussed by Stephan Stolz. It implies the so-called 'stable Gromov-Lawson-Rosenberg conjecture'. The unstable version of this conjecture said that, given a closed spin manifold M, a certain obstruction, living in a certain (topological) K-theory group, vanishes if and only M admits a Riemannian metric with positive scalar curvature. It turns out that this is wrong, and counterexamples will be presented in the second chapter. The third chapter introduces another set of invariants, also using operator algebra techniques, namely L 2 -cohomology, L 2 -Betti numbers and other L 2 -invariants. These invariants, their basic properties, and the central questions about them, are introduced in the third chapter. (author)
Algebraic Modeling of Topological and Computational Structures and Applications
Theodorou, Doros; Stefaneas, Petros; Kauffman, Louis
2017-01-01
This interdisciplinary book covers a wide range of subjects, from pure mathematics (knots, braids, homotopy theory, number theory) to more applied mathematics (cryptography, algebraic specification of algorithms, dynamical systems) and concrete applications (modeling of polymers and ionic liquids, video, music and medical imaging). The main mathematical focus throughout the book is on algebraic modeling with particular emphasis on braid groups. The research methods include algebraic modeling using topological structures, such as knots, 3-manifolds, classical homotopy groups, and braid groups. The applications address the simulation of polymer chains and ionic liquids, as well as the modeling of natural phenomena via topological surgery. The treatment of computational structures, including finite fields and cryptography, focuses on the development of novel techniques. These techniques can be applied to the design of algebraic specifications for systems modeling and verification. This book is the outcome of a w...
Advanced modern algebra part 2
Rotman, Joseph J
2017-01-01
This book is the second part of the new edition of Advanced Modern Algebra (the first part published as Graduate Studies in Mathematics, Volume 165). Compared to the previous edition, the material has been significantly reorganized and many sections have been rewritten. The book presents many topics mentioned in the first part in greater depth and in more detail. The five chapters of the book are devoted to group theory, representation theory, homological algebra, categories, and commutative algebra, respectively. The book can be used as a text for a second abstract algebra graduate course, as a source of additional material to a first abstract algebra graduate course, or for self-study.
International Nuclear Information System (INIS)
Ogievetsky, O.; Schmidke, W.B.; Wess, J.; Muenchen Univ.; Zumino, B.; Lawrence Berkeley Lab., CA
1992-01-01
The q-differential calculus for the q-Minkowski space is developed. The algebra of the q-derivatives with the q-Lorentz generators is found giving the q-deformation of the Poincare algebra. The reality structure of the q-Poincare algebra is given. The reality structure of the q-differentials is also found. The real Laplaacian is constructed. Finally the comultiplication, counit and antipode for the q-Poincare algebra are obtained making it a Hopf algebra. (orig.)
Directory of Open Access Journals (Sweden)
A. Averbuch
1994-01-01
Full Text Available Parallel elliptic single/multigrid solutions around an aligned and nonaligned body are presented and implemented on two multi-user and single-user shared memory multiprocessors (Sequent Symmetry and MOS and on a distributed memory multiprocessor (a Transputer network. Our parallel implementation uses the Virtual Machine for Muli-Processors (VMMP, a software package that provides a coherent set of services for explicitly parallel application programs running on diverse multiple instruction multiple data (MIMD multiprocessors, both shared memory and message passing. VMMP is intended to simplify parallel program writing and to promote portable and efficient programming. Furthermore, it ensures high portability of application programs by implementing the same services on all target multiprocessors. The performance of our algorithm is investigated in detail. It is seen to fit well the above architectures when the number of processors is less than the maximal number of grid points along the axes. In general, the efficiency in the nonaligned case is higher than in the aligned case. Alignment overhead is observed to be up to 200% in the shared-memory case and up to 65% in the message-passing case. We have demonstrated that when using VMMP, the portability of the algorithms is straightforward and efficient.
Yildiz Ulus, Aysegul
2013-01-01
This paper examines experimental and algorithmic contributions of advanced calculators (graphing and computer algebra system, CAS) in teaching the concept of "diagonalization," one of the key topics in Linear Algebra courses taught at the undergraduate level. Specifically, the proposed hypothesis of this study is to assess the effective…
Algebra of 2D periodic operators with local and perpendicular defects
DEFF Research Database (Denmark)
Kutsenko, Anton
2016-01-01
We show that 2D periodic operators with local and perpendicular defects form an algebra. We provide an algorithm for finding spectrum for such operators. While the continuous spectral components can be computed by simple algebraic operations on some matrix-valued functions and a few number...
Hopf algebras in noncommutative geometry
International Nuclear Information System (INIS)
Varilly, Joseph C.
2001-10-01
We give an introductory survey to the use of Hopf algebras in several problems of non- commutative geometry. The main example, the Hopf algebra of rooted trees, is a graded, connected Hopf algebra arising from a universal construction. We show its relation to the algebra of transverse differential operators introduced by Connes and Moscovici in order to compute a local index formula in cyclic cohomology, and to the several Hopf algebras defined by Connes and Kreimer to simplify the combinatorics of perturbative renormalization. We explain how characteristic classes for a Hopf module algebra can be obtained from the cyclic cohomology of the Hopf algebra which acts on it. Finally, we discuss the theory of non- commutative spherical manifolds and show how they arise as homogeneous spaces of certain compact quantum groups. (author)
On Dunkl angular momenta algebra
Energy Technology Data Exchange (ETDEWEB)
Feigin, Misha [School of Mathematics and Statistics, University of Glasgow,15 University Gardens, Glasgow G12 8QW (United Kingdom); Hakobyan, Tigran [Yerevan State University,1 Alex Manoogian, 0025 Yerevan (Armenia); Tomsk Polytechnic University,Lenin Ave. 30, 634050 Tomsk (Russian Federation)
2015-11-17
We consider the quantum angular momentum generators, deformed by means of the Dunkl operators. Together with the reflection operators they generate a subalgebra in the rational Cherednik algebra associated with a finite real reflection group. We find all the defining relations of the algebra, which appear to be quadratic, and we show that the algebra is of Poincaré-Birkhoff-Witt (PBW) type. We show that this algebra contains the angular part of the Calogero-Moser Hamiltonian and that together with constants it generates the centre of the algebra. We also consider the gl(N) version of the subalgebra of the rational Cherednik algebra and show that it is a non-homogeneous quadratic algebra of PBW type as well. In this case the central generator can be identified with the usual Calogero-Moser Hamiltonian associated with the Coxeter group in the harmonic confinement.
Continuum analogues of contragredient Lie algebras
International Nuclear Information System (INIS)
Saveliev, M.V.; Vershik, A.M.
1989-03-01
We present an axiomatic formulation of a new class of infinite-dimensional Lie algebras - the generalizations of Z-graded Lie algebras with, generally speaking, an infinite-dimensional Cartan subalgebra and a contiguous set of roots. We call such algebras ''continuum Lie algebras''. The simple Lie algebras of constant growth are encapsulated in our formulation. We pay particular attention to the case when the local algebra is parametrized by a commutative algebra while the Cartan operator (the generalization of the Cartan matrix) is a linear operator. Special examples of these algebras are the Kac-Moody algebras, algebras of Poisson brackets, algebras of vector fields on a manifold, current algebras, and algebras with differential or integro-differential Cartan operator. The nonlinear dynamical systems associated with the continuum contragredient Lie algebras are also considered. (author). 9 refs
Conservative multigrid methods for Cahn-Hilliard fluids
International Nuclear Information System (INIS)
Kim, Junseok; Kang, Kyungkeun; Lowengrub, John
2004-01-01
We develop a conservative, second-order accurate fully implicit discretization of the Navier-Stokes (NS) and Cahn-Hilliard (CH) system that has an associated discrete energy functional. This system provides a diffuse-interface description of binary fluid flows with compressible or incompressible flow components [R. Soc. Lond. Proc. Ser. A Math. Phys. Eng. Sci. 454 (1998) 2617]. In this work, we focus on the case of flows containing two immiscible, incompressible and density-matched components. The scheme, however, has a straightforward extension to multi-component systems. To efficiently solve the discrete system at the implicit time-level, we develop a nonlinear multigrid method to solve the CH equation which is then coupled to a projection method that is used to solve the NS equation. We demonstrate convergence of our scheme numerically in both the presence and absence of flow and perform simulations of phase separation via spinodal decomposition. We examine the separate effects of surface tension and external flow on the decomposition. We find surface tension driven flow alone increases coalescence rates through the retraction of interfaces. When there is an applied external shear, the evolution of the flow is nontrivial and the flow morphology repeats itself in time as multiple pinchoff and reconnection events occur. Eventually, the periodic motion ceases and the system relaxes to a global equilibrium. The equilibria we observe appears has a similar structure in all cases although the dynamics of the evolution is quite different. We view the work presented in this paper as preparatory for a detailed investigation of liquid-liquid interfaces with surface tension where the interfaces separate two immiscible fluids [On the pinchoff of liquid-liquid jets with surface tension, in preparation]. To this end, we also include a simulation of the pinchoff of a liquid thread under the Rayleigh instability at finite Reynolds number
International Nuclear Information System (INIS)
Marquette, Ian
2013-01-01
We introduce the most general quartic Poisson algebra generated by a second and a fourth order integral of motion of a 2D superintegrable classical system. We obtain the corresponding quartic (associative) algebra for the quantum analog, extend Daskaloyannis construction obtained in context of quadratic algebras, and also obtain the realizations as deformed oscillator algebras for this quartic algebra. We obtain the Casimir operator and discuss how these realizations allow to obtain the finite-dimensional unitary irreducible representations of quartic algebras and obtain algebraically the degenerate energy spectrum of superintegrable systems. We apply the construction and the formula obtained for the structure function on a superintegrable system related to type I Laguerre exceptional orthogonal polynomials introduced recently
Development of new multigrid schemes for the method of characteristics in neutron transport theory
International Nuclear Information System (INIS)
Grassi, G.
2006-01-01
This dissertation is based upon our doctoral research that dealt with the conception and development of new non-linear multigrid techniques for the Method of the Characteristics (MOC) within the TDT code. Here we focus upon a two-level scheme consisting of a fine level on which the neutron transport equation is iteratively solved using the MOC algorithm, and a coarse level defined by a more coarsely discretized phase space on which a low-order problem is considered. The solution of this problem is then used in order to correct the angular flux moments resulting from the previous transport iteration. A flux-volume homogenization procedure is employed to evaluate the coarse-level material properties after each transport iteration. This entails the non-linearity of the methods. According to the Generalised Equivalence Theory (GET), additional degrees of freedom are introduced for the low-order problem so that the convergence of the acceleration scheme can be ensured. We present two classes of non-linear methods: transport-like methods and discussion-like methods. Transport-like methods consider a homogenized low-order transport problem on the coarse level. This problem is iteratively solved using the same MOC algorithm as for the transport problem on the fine level. Discontinuity factors are then employed, per region or per surface, in order to reconstruct the currents evaluated by the low-order operator, which ensure the convergence of the acceleration scheme. On the other hand, discussion-like methods consider a low-order problem inspired by diffusion. We studied the non-linear Coarse Mesh Finite Difference (CMFD) method, already present in literature, in the perspective of integrating it into TDT code. Then, we developed a new non-linear method on the model of CMFD. From the latter, we borrowed the idea to establish a simple relation between currents and fluxes in order to obtain a problem involving only coarse fluxes. Finally, those non-linear methods have been
Some nonlinear space decomposition algorithms
Energy Technology Data Exchange (ETDEWEB)
Tai, Xue-Cheng; Espedal, M. [Univ. of Bergen (Norway)
1996-12-31
Convergence of a space decomposition method is proved for a general convex programming problem. The space decomposition refers to methods that decompose a space into sums of subspaces, which could be a domain decomposition or a multigrid method for partial differential equations. Two algorithms are proposed. Both can be used for linear as well as nonlinear elliptic problems and they reduce to the standard additive and multiplicative Schwarz methods for linear elliptic problems. Two {open_quotes}hybrid{close_quotes} algorithms are also presented. They converge faster than the additive one and have better parallelism than the multiplicative method. Numerical tests with a two level domain decomposition for linear, nonlinear and interface elliptic problems are presented for the proposed algorithms.
Bochnak, Jacek; Roy, Marie-Françoise
1998-01-01
This book is a systematic treatment of real algebraic geometry, a subject that has strong interrelation with other areas of mathematics: singularity theory, differential topology, quadratic forms, commutative algebra, model theory, complexity theory etc. The careful and clearly written account covers both basic concepts and up-to-date research topics. It may be used as text for a graduate course. The present edition is a substantially revised and expanded English version of the book "Géometrie algébrique réelle" originally published in French, in 1987, as Volume 12 of ERGEBNISSE. Since the publication of the French version the theory has made advances in several directions. Many of these are included in this English version. Thus the English book may be regarded as a completely new treatment of the subject.
Directory of Open Access Journals (Sweden)
María Carolina Spinel G.
1990-01-01
Con esta base, en posteriores artículos de divulgación, presentaremos algunas aplicaciones que muestren la ventaja de su empleo en la descripción de sistema físico. Dado el amplio conocimiento que se tiene de los espacios vectoriales. La estructura y propiedades del algebra de Clifford suele presentarse con base en los elementos de un espacio vectorial. En esta dirección, en la sección 2 se define la notación y se describe la estructura de un algebra de Clifford Gn, introduciendo con detalle las operaciones básicas entre los elementos del álgebra. La sección 3 se dedica a describir una base tensorial de Gn.
Hano, Mitsuo; Hotta, Masashi
A new multigrid method based on high-order vector finite elements is proposed in this paper. Low level discretizations in this method are obtained by using low-order vector finite elements for the same mesh. Gauss-Seidel method is used as a smoother, and a linear equation of lowest level is solved by ICCG method. But it is often found that multigrid solutions do not converge into ICCG solutions. An elimination algolithm of constant term using a null space of the coefficient matrix is also described. In three dimensional magnetostatic field analysis, convergence time and number of iteration of this multigrid method are discussed with the convectional ICCG method.
Indian Academy of Sciences (India)
project of the Spanish Ministerio de Educación y Ciencia MTM2007-60333. References. [1] Calderón A J, On split Lie algebras with symmetric root systems, Proc. Indian. Acad. Sci (Math. Sci.) 118(2008) 351–356. [2] Calderón A J, On split Lie triple systems, Proc. Indian. Acad. Sci (Math. Sci.) 119(2009). 165–177.
Lee, Jaehoon; Wilczek, Frank
2013-11-27
Motivated by the problem of identifying Majorana mode operators at junctions, we analyze a basic algebraic structure leading to a doubled spectrum. For general (nonlinear) interactions the emergent mode creation operator is highly nonlinear in the original effective mode operators, and therefore also in the underlying electron creation and destruction operators. This phenomenon could open up new possibilities for controlled dynamical manipulation of the modes. We briefly compare and contrast related issues in the Pfaffian quantum Hall state.
Beigie, Darin
2014-01-01
Most people who are attracted to STEM-related fields are drawn not by a desire to take mathematics tests but to create things. The opportunity to create an algebra drawing gives students a sense of ownership and adventure that taps into the same sort of energy that leads a young person to get lost in reading a good book, building with Legos®,…
Fundamentals of linear algebra
Dash, Rajani Ballav
2008-01-01
FUNDAMENTALS OF LINEAR ALGEBRA is a comprehensive Text Book, which can be used by students and teachers of All Indian Universities. The Text has easy, understandable form and covers all topics of UGC Curriculum. There are lots of worked out examples which helps the students in solving the problems without anybody's help. The Problem sets have been designed keeping in view of the questions asked in different examinations.
Algebras of Information States
Czech Academy of Sciences Publication Activity Database
Punčochář, Vít
2017-01-01
Roč. 27, č. 5 (2017), s. 1643-1675 ISSN 0955-792X R&D Projects: GA ČR(CZ) GC16-07954J Institutional support: RVO:67985955 Keywords : information states * relational semantics * algebraic semantics * intuitionistic logic * inquisitive disjunction Subject RIV: AA - Philosophy ; Religion OBOR OECD: Philosophy, History and Philosophy of science and technology Impact factor: 0.909, year: 2016
International Nuclear Information System (INIS)
Todorov, Ivan
2010-12-01
Expository notes on Clifford algebras and spinors with a detailed discussion of Majorana, Weyl, and Dirac spinors. The paper is meant as a review of background material, needed, in particular, in now fashionable theoretical speculations on neutrino masses. It has a more mathematical flavour than the over twenty-six-year-old Introduction to Majorana masses [M84] and includes historical notes and biographical data on past participants in the story. (author)
Algebra & trigonometry II essentials
REA, Editors of
2012-01-01
REA's Essentials provide quick and easy access to critical information in a variety of different fields, ranging from the most basic to the most advanced. As its name implies, these concise, comprehensive study guides summarize the essentials of the field covered. Essentials are helpful when preparing for exams, doing homework and will remain a lasting reference source for students, teachers, and professionals. Algebra & Trigonometry II includes logarithms, sequences and series, permutations, combinations and probability, vectors, matrices, determinants and systems of equations, mathematica
Lutfiyya, Lutfi A
2012-01-01
REA's Essentials provide quick and easy access to critical information in a variety of different fields, ranging from the most basic to the most advanced. As its name implies, these concise, comprehensive study guides summarize the essentials of the field covered. Essentials are helpful when preparing for exams, doing homework and will remain a lasting reference source for students, teachers, and professionals. Modern Algebra includes set theory, operations, relations, basic properties of the integers, group theory, and ring theory.
A Multigrid NLS-4DVar Data Assimilation Scheme with Advanced Research WRF (ARW)
Zhang, H.; Tian, X.
2017-12-01
The motions of the atmosphere have multiscale properties in space and/or time, and the background error covariance matrix (Β) should thus contain error information at different correlation scales. To obtain an optimal analysis, the multigrid three-dimensional variational data assimilation scheme is used widely when sequentially correcting errors from large to small scales. However, introduction of the multigrid technique into four-dimensional variational data assimilation is not easy, due to its strong dependence on the adjoint model, which has extremely high computational costs in data coding, maintenance, and updating. In this study, the multigrid technique was introduced into the nonlinear least-squares four-dimensional variational assimilation (NLS-4DVar) method, which is an advanced four-dimensional ensemble-variational method that can be applied without invoking the adjoint models. The multigrid NLS-4DVar (MG-NLS-4DVar) scheme uses the number of grid points to control the scale, with doubling of this number when moving from a coarse to a finer grid. Furthermore, the MG-NLS-4DVar scheme not only retains the advantages of NLS-4DVar, but also sufficiently corrects multiscale errors to achieve a highly accurate analysis. The effectiveness and efficiency of the proposed MG-NLS-4DVar scheme were evaluated by several groups of observing system simulation experiments using the Advanced Research Weather Research and Forecasting Model. MG-NLS-4DVar outperformed NLS-4DVar, with a lower computational cost.
Monolithic multigrid method for the coupled Stokes flow and deformable porous medium system
P. Luo (Peiyao); C. Rodrigo (Carmen); F.J. Gaspar Lorenz (Franscisco); C.W. Oosterlee (Cornelis)
2018-01-01
textabstractThe interaction between fluid flow and a deformable porous medium is a complicated multi-physics problem, which can be described by a coupled model based on the Stokes and poroelastic equations. A monolithic multigrid method together with either a coupled Vanka smoother or a decoupled
Analysis of preconditioning and multigrid for Euler flows with low-subsonic regions
Koren, B.; Leer, van B.
1995-01-01
For subsonic flows and upwind-discretized, linearized 1-D Euler equations, the smoothing behavior of multigrid-accelerated point Gauss-Seidel relaxation is analyzed. Error decay by convection across domain boundaries is also discussed. A fix to poor convergence rates at low Mach numbers is sought in
Two-level Fourier analysis of a multigrid approach for discontinuous Galerkin discretisation
P.W. Hemker (Piet); W. Hoffmann; M.H. van Raalte (Marc)
2002-01-01
textabstractIn this paper we study a multigrid method for the solution of a linear second order elliptic equation, discretized by discontinuous Galerkin (DG) methods, andwe give a detailed analysis of the convergence for different block-relaxation strategies.We find that point-wise
A multigrid based 3D space-charge routine in the tracking code GPT
Pöplau, G.; Rienen, van U.; Loos, de M.J.; Geer, van der S.B.; Berz, M.; Makino, K.
2005-01-01
Fast calculation of3D non-linear space-charge fields is essential for the simulation ofhigh-brightness charged particle beams. We report on our development of a new 3D spacecharge routine in the General Particle Tracer (GPT) code. The model is based on a nonequidistant multigrid Poisson solver that
DEFF Research Database (Denmark)
Kolmogorov, Dmitry; Sørensen, Niels N.; Shen, Wen Zhong
2013-01-01
An Optimized Schwarz method using Robin boundary conditions for relaxation scheme is presented in the frame of Multigrid method on discontinuous grids. At each iteration the relaxation scheme is performed in two steps: one step with Dirichlet and another step with Robin boundary conditions at inn...
A multigrid Newton-Krylov method for flux-limited radiation diffusion
International Nuclear Information System (INIS)
Rider, W.J.; Knoll, D.A.; Olson, G.L.
1998-01-01
The authors focus on the integration of radiation diffusion including flux-limited diffusion coefficients. The nonlinear integration is accomplished with a Newton-Krylov method preconditioned with a multigrid Picard linearization of the governing equations. They investigate the efficiency of the linear and nonlinear iterative techniques
Blyth, T S
2002-01-01
Most of the introductory courses on linear algebra develop the basic theory of finite dimensional vector spaces, and in so doing relate the notion of a linear mapping to that of a matrix. Generally speaking, such courses culminate in the diagonalisation of certain matrices and the application of this process to various situations. Such is the case, for example, in our previous SUMS volume Basic Linear Algebra. The present text is a continuation of that volume, and has the objective of introducing the reader to more advanced properties of vector spaces and linear mappings, and consequently of matrices. For readers who are not familiar with the contents of Basic Linear Algebra we provide an introductory chapter that consists of a compact summary of the prerequisites for the present volume. In order to consolidate the student's understanding we have included a large num ber of illustrative and worked examples, as well as many exercises that are strategi cally placed throughout the text. Solutions to the ex...
s-Step Krylov Subspace Methods as Bottom Solvers for Geometric Multigrid
Energy Technology Data Exchange (ETDEWEB)
Williams, Samuel [Lawrence Berkeley National Lab. (LBNL), Berkeley, CA (United States); Lijewski, Mike [Lawrence Berkeley National Lab. (LBNL), Berkeley, CA (United States); Almgren, Ann [Lawrence Berkeley National Lab. (LBNL), Berkeley, CA (United States); Straalen, Brian Van [Lawrence Berkeley National Lab. (LBNL), Berkeley, CA (United States); Carson, Erin [Univ. of California, Berkeley, CA (United States); Knight, Nicholas [Univ. of California, Berkeley, CA (United States); Demmel, James [Univ. of California, Berkeley, CA (United States)
2014-08-14
Geometric multigrid solvers within adaptive mesh refinement (AMR) applications often reach a point where further coarsening of the grid becomes impractical as individual sub domain sizes approach unity. At this point the most common solution is to use a bottom solver, such as BiCGStab, to reduce the residual by a fixed factor at the coarsest level. Each iteration of BiCGStab requires multiple global reductions (MPI collectives). As the number of BiCGStab iterations required for convergence grows with problem size, and the time for each collective operation increases with machine scale, bottom solves in large-scale applications can constitute a significant fraction of the overall multigrid solve time. In this paper, we implement, evaluate, and optimize a communication-avoiding s-step formulation of BiCGStab (CABiCGStab for short) as a high-performance, distributed-memory bottom solver for geometric multigrid solvers. This is the first time s-step Krylov subspace methods have been leveraged to improve multigrid bottom solver performance. We use a synthetic benchmark for detailed analysis and integrate the best implementation into BoxLib in order to evaluate the benefit of a s-step Krylov subspace method on the multigrid solves found in the applications LMC and Nyx on up to 32,768 cores on the Cray XE6 at NERSC. Overall, we see bottom solver improvements of up to 4.2x on synthetic problems and up to 2.7x in real applications. This results in as much as a 1.5x improvement in solver performance in real applications.