Search

Your search keyword '"block cyclic reduction"' showing total 19 results
Start Over Descriptor "block cyclic reduction"
19 results on '"block cyclic reduction"'

1. Roots of Characteristic Polynomial Sequences in Iterative Block Cyclic Reductions

Author

Masato Shinjo, Tan Wang, Masashi Iwasaki, and Yoshimasa Nakamura

Subjects
block cyclic reduction, block tridiagonal matrix, characteristic polynomial, linear system, Mathematics, QA1-939
Abstract

The block cyclic reduction method is a finite-step direct method used for solving linear systems with block tridiagonal coefficient matrices. It iteratively uses transformations to reduce the number of non-zero blocks in coefficient matrices. With repeated block cyclic reductions, non-zero off-diagonal blocks in coefficient matrices incrementally leave the diagonal blocks and eventually vanish after a finite number of block cyclic reductions. In this paper, we focus on the roots of characteristic polynomials of coefficient matrices that are repeatedly transformed by block cyclic reductions. We regard each block cyclic reduction as a composition of two types of matrix transformations, and then attempt to examine changes in the existence range of roots. This is a block extension of the idea presented in our previous papers on simple cyclic reductions. The property that the roots are not very scattered is a key to accurately solve linear systems in floating-point arithmetic. We clarify that block cyclic reductions do not disperse roots, but rather narrow their distribution, if the original coefficient matrix is symmetric positive or negative definite.

Published
2021
Full Text
View/download PDF

2. A note on the fast direct method for discrete elliptic problems.

Author

Goreinov, Sergei A.

Subjects
*LOW-rank matrices, *DIGITAL signatures, *KRONECKER products, *DATA distribution, *MAGNITUDE (Mathematics), *LINEAR systems
Abstract

We consider a method due to P. Vassilevski and Yu. A. Kuznetsov [4, 10] for solving linear systems with matrices of low Kronecker rank such that all factors in Kronecker products are banded. Most important examples of such matrices arise from discretized div K grad operator with diffusion term k1(x)k2(y)k3(z). Several practical issues are addressed: an MPI implementation with distribution of data along processor grid inheriting Cartesian 3D structure of discretized problem; implicit deflation of the known nullspace of the system matrix; links with two-grid framework of multigrid algorithm which allow one to remove the requirement of Kronecker structure in one or two of axes. Numerical experiments show the efficiency of 3D data distribution having the scalability analogous to (structured) HYPRE solvers yet the absolute timings being an order of magnitude lower, on the range from 10 to 104 cores. [ABSTRACT FROM AUTHOR]

Published
2019
Full Text
View/download PDF

3. Parallel Solution of Narrow Banded Diagonally Dominant Linear Systems

Author

Mikkelsen, Carl Christian Kjelgaard, Kågström, Bo, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, and Jónasson, Kristján, editor

Published
2012
Full Text
View/download PDF

4. Quantum Simulation of Quantum Effects in Sub-10-nm Transistor Technologies

Abstract

In this master thesis, a 2D device simulator run on a hybrid classical-quantum computer was developed. The simulator was developed to treat statistical quantum effects such as quantum tunneling and quantum confinement in nanoscale transistors. The simulation scheme is based on a self-consistent solution of the coupled non-linear 2D SchrödingerPoisson equations. The Open Boundary Condition (OBC) of the Schrödinger equation, which allows for electrons to pass through the device between the leads (source and drain), are modeled with the QuantumTransmitting Boundary Method (QTBM). The differential equations are discretized with the finite-element method, using rectangular mesh elements. The self-consistent loop is a very time-consuming process, mainly due to the solution of the discretized OBC Schrödinger equation. To accelerate the solution time of the Schrödinger equation, a quantum assisted domain decomposition method is implemented. The domain decomposition method of choice is the Block Cyclic Reduction (BCR) method. The BCR method is at least 15 times faster (CPU time) than solving the whole linear system of equations with the Python solver numpy.linalg.solve, based on the LAPACK routine _gesv. In the project, we also propose an alternative approach of the BCR method called the "extra layer BCR" that shows an improved accuracy for certain types of solutions. In a quantum assisted version, the matrix inverse solver as a step in the BCR method was computed on the D-Wave quantum annealer chip ADVANTAGE_SYSTEM4.1 [4]. Two alternative methods to solve the matrix inverses on a quantum annealer were compared. One is called the "unit vector" approach, based on work by Rogers and Singleton [5], and the other is called the "whole matrix" approach which was developed in the thesis. Because of the limited amount of qubits available on the quantum annealer, the "unit vector" approach was more suitable for adaption in the BCR method. Comparing the quantum annealer to the Python

Published
2022

5. Quantum Simulation of Quantum Effects in Sub-10-nm Transistor Technologies

Abstract

In this master thesis, a 2D device simulator run on a hybrid classical-quantum computer was developed. The simulator was developed to treat statistical quantum effects such as quantum tunneling and quantum confinement in nanoscale transistors. The simulation scheme is based on a self-consistent solution of the coupled non-linear 2D SchrödingerPoisson equations. The Open Boundary Condition (OBC) of the Schrödinger equation, which allows for electrons to pass through the device between the leads (source and drain), are modeled with the QuantumTransmitting Boundary Method (QTBM). The differential equations are discretized with the finite-element method, using rectangular mesh elements. The self-consistent loop is a very time-consuming process, mainly due to the solution of the discretized OBC Schrödinger equation. To accelerate the solution time of the Schrödinger equation, a quantum assisted domain decomposition method is implemented. The domain decomposition method of choice is the Block Cyclic Reduction (BCR) method. The BCR method is at least 15 times faster (CPU time) than solving the whole linear system of equations with the Python solver numpy.linalg.solve, based on the LAPACK routine _gesv. In the project, we also propose an alternative approach of the BCR method called the "extra layer BCR" that shows an improved accuracy for certain types of solutions. In a quantum assisted version, the matrix inverse solver as a step in the BCR method was computed on the D-Wave quantum annealer chip ADVANTAGE_SYSTEM4.1 [4]. Two alternative methods to solve the matrix inverses on a quantum annealer were compared. One is called the "unit vector" approach, based on work by Rogers and Singleton [5], and the other is called the "whole matrix" approach which was developed in the thesis. Because of the limited amount of qubits available on the quantum annealer, the "unit vector" approach was more suitable for adaption in the BCR method. Comparing the quantum annealer to the Python

Published
2022

6. Quantum Simulation of Quantum Effects in Sub-10-nm Transistor Technologies

Author

Winka, Anders

Subjects
Quantum Transport, Block Cyclic Reduction, Quantum Annealer, Transistor Modeling, Quantum Computing, Condensed Matter Physics, Den kondenserade materiens fysik, QTBM
Abstract

In this master thesis, a 2D device simulator run on a hybrid classical-quantum computer was developed. The simulator was developed to treat statistical quantum effects such as quantum tunneling and quantum confinement in nanoscale transistors. The simulation scheme is based on a self-consistent solution of the coupled non-linear 2D SchrödingerPoisson equations. The Open Boundary Condition (OBC) of the Schrödinger equation, which allows for electrons to pass through the device between the leads (source and drain), are modeled with the QuantumTransmitting Boundary Method (QTBM). The differential equations are discretized with the finite-element method, using rectangular mesh elements. The self-consistent loop is a very time-consuming process, mainly due to the solution of the discretized OBC Schrödinger equation. To accelerate the solution time of the Schrödinger equation, a quantum assisted domain decomposition method is implemented. The domain decomposition method of choice is the Block Cyclic Reduction (BCR) method. The BCR method is at least 15 times faster (CPU time) than solving the whole linear system of equations with the Python solver numpy.linalg.solve, based on the LAPACK routine _gesv. In the project, we also propose an alternative approach of the BCR method called the "extra layer BCR" that shows an improved accuracy for certain types of solutions. In a quantum assisted version, the matrix inverse solver as a step in the BCR method was computed on the D-Wave quantum annealer chip ADVANTAGE_SYSTEM4.1 [4]. Two alternative methods to solve the matrix inverses on a quantum annealer were compared. One is called the "unit vector" approach, based on work by Rogers and Singleton [5], and the other is called the "whole matrix" approach which was developed in the thesis. Because of the limited amount of qubits available on the quantum annealer, the "unit vector" approach was more suitable for adaption in the BCR method. Comparing the quantum annealer to the Python inverse solver numpy.linalg.inv, also based on LAPACK, it was found that an accurate solution can be achieved, but the simulation time (CPU time) is at best 500 times slower than numpy.linalg.inv.

Published
2022

7. A discontinuous Galerkin method with block cyclic reduction solver for simulating compressible flows on GPUs.

Author

Baghapour, Behzad, Esfahanian, Vahid, Torabzadeh, Mohammad, and Mahmoodi Darian, Hossein

Subjects
*GALERKIN methods, *GRAPHICS processing units, *RUN time systems (Computer science), *MOTHERBOARDS, *PERFORMANCE evaluation
Abstract

An optimized implementation of a block tridiagonal solver based on the block cyclic reduction (BCR) algorithm is introduced and its portability to graphics processing units (GPUs) is explored. The computations are performed on the NVIDIA GTX480 GPU. The results are compared with those obtained on a single core of Intel Core i7-920 (2.67 GHz) in terms of calculation runtime. The BCR linear solver achieves the maximum speedup of 5.84x with block size of 32 over the CPU Thomas algorithm in double precision. The proposed BCR solver is applied to discontinuous Galerkin (DG) simulations on structured grids via alternating direction implicit (ADI) scheme. The GPU performance of the entire computational fluid dynamics (CFD) code is studied for different compressible inviscid flow test cases. For a general mesh with quadrilateral elements, the ADI-DG solver achieves the maximum total speedup of 7.45x for the piecewise quadratic solution over the CPU platform in double precision. [ABSTRACT FROM AUTHOR]

Published
2015
Full Text
View/download PDF

8. A parallel radix-4 block cyclic reduction algorithm.

Author

Myllykoski, M. and Rossi, T.

Subjects
*PARALLEL algorithms, *LINEAR systems, *NUMBER theory, *PARALLEL processing, *COEFFICIENTS (Statistics), *MATRICES (Mathematics), *POISSON'S equation
Abstract

SUMMARY A conventional block cyclic reduction algorithm operates by halving the size of the linear system at each reduction step, that is, the algorithm is a radix-2 method. An algorithm analogous to the block cyclic reduction known as the radix-q partial solution variant of the cyclic reduction (PSCR) method allows the use of higher radix numbers and is thus more suitable for parallel architectures as it requires fever reduction steps. This paper presents an alternative and more intuitive way of deriving a radix-4 block cyclic reduction method for systems with a coefficient matrix of the form tridiag{ − I, D, − I}. This is performed by modifying an existing radix-2 block cyclic reduction method. The resulting algorithm is then parallelized by using the partial fraction technique. The parallel variant is demonstrated to be less computationally expensive when compared to the radix-2 block cyclic reduction method in the sense that the total number of emerging subproblems is reduced. The method is also shown to be numerically stable and equivalent to the radix-4 PSCR method. The numerical results archived correspond to the theoretical expectations. Copyright © 2013 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Published
2014
Full Text
View/download PDF

9. Roots of Characteristic Polynomial Sequences in Iterative Block Cyclic Reductions.

Author

Shinjo, Masato, Wang, Tan, Iwasaki, Masashi, and Nakamura, Yoshimasa

Subjects
*FLOATING-point arithmetic, *POLYNOMIALS, *SYMMETRIC matrices, *LINEAR systems
Abstract

The block cyclic reduction method is a finite-step direct method used for solving linear systems with block tridiagonal coefficient matrices. It iteratively uses transformations to reduce the number of non-zero blocks in coefficient matrices. With repeated block cyclic reductions, non-zero off-diagonal blocks in coefficient matrices incrementally leave the diagonal blocks and eventually vanish after a finite number of block cyclic reductions. In this paper, we focus on the roots of characteristic polynomials of coefficient matrices that are repeatedly transformed by block cyclic reductions. We regard each block cyclic reduction as a composition of two types of matrix transformations, and then attempt to examine changes in the existence range of roots. This is a block extension of the idea presented in our previous papers on simple cyclic reductions. The property that the roots are not very scattered is a key to accurately solve linear systems in floating-point arithmetic. We clarify that block cyclic reductions do not disperse roots, but rather narrow their distribution, if the original coefficient matrix is symmetric positive or negative definite. [ABSTRACT FROM AUTHOR]

Published
2021
Full Text
View/download PDF

10. A NONSTANDARD CYCLIC REDUCTION METHOD, ITS VARIANTS AND STABILITY.

Author

Rossi, Tuomo and Toivanen, Jari

Subjects
*MATRICES (Mathematics), *POISSON algebras, *PROBLEM solving, *FACTORIZATION, *NUMERICAL solutions to Poisson's equation, *MATHEMATICS
Abstract

A nonstandard cyclic reduction method is introduced for solving the Poisson equation in rectangular domains. Different ways of solving the arising reduced systems are considered. The partial solution approach leads to the so-called partial solution variant of the cyclic reduction (PSCR) method, while the other variants are obtained by using the matrix rational polynomial factorization technique, including the partial fraction expansions, the fast Fourier transform (FFT) approach, and the combination of Fourier analysis and cyclic reduction (FACR) techniques. Such techniques have originally been considered in the standard cyclic reduction framework. The equivalence of the partial solution and the partial fraction techniques is shown. The computational cost of the considered variants is O(N log N) operations, except for the FACR techniques for which it is O(N log log N). The stability estimate for the considered method is constructed, and the stability is demonstrated by numerical experiments. [ABSTRACT FROM AUTHOR]

Published
1999
Full Text
View/download PDF

11. On GPU-accelerated fast direct solvers and their applications in image denoising

Author

Mirko Myllykoski

Subjects
block cyclic reduction, näytönohjaimet, OpenCL, numeeriset menetelmät, prosessorit, image denoising, parallel computing, mean curvature, GPU computing, kuvankäsittely, image processing, fast Poisson solver, separable block tridiagonal linear system, PSCR method, optimointi, algoritmit, ohjelmointi, augmented Lagrangian method, kohina, fast direct solver, rinnakkaislaskenta, alternating direction methods of multipliers
Published
2015

12. A parallel radix-4 block cyclic reduction algorithm

Author

Myllykoski, Mirko and Rossi, Tuomo

Subjects
fast Poisson solver, block cyclic reduction, nopea Poisson ratkaisija, osamurtokehitelmätekniikka, parallel computing, syklinen reduktio, PSCR, rinnakkaislaskenta, suora ratkaisija, direct solver, partial fraction technique
Abstract

A conventional block cyclic reduction algorithm operates by halving the size of the linear system at each reduction step, that is, the algorithm is a radix-2 method. An algorithm analogous to the block cyclic reduction known as the radix-q partial solution variant of the cyclic reduction (PSCR) method allows the use of higher radix numbers and is thus more suitable for parallel architectures as it requires fever reduction steps. This paper presents an alternative and more intuitive way of deriving a radix-4 block cyclic reduction method for systems with a coefficient matrix of the form tridiag{ − I,D, − I}. This is performed by modifying an existing radix-2 block cyclic reduction method. The resulting algorithm is then parallelized by using the partial fraction technique. The parallel variant is demonstrated to be less computationally expensive when compared to the radix-2 block cyclic reduction method in the sense that the total number of emerging subproblems is reduced. The method is also shown to be numerically stable and equivalent to the radix-4 PSCR method. The numerical results archived correspond to the theoretical expectations. peerReviewed

Published
2014

13. Parallel Solution of Narrow Banded Diagonally Dominant Linear Systems

Author

Carl Christian Kjelgaard Mikkelsen and Bo Kågström

Subjects
block cyclic reduction, Computer Sciences, ScaLAPACK, Truncation error (numerical integration), Linear system, MathematicsofComputing_NUMERICALANALYSIS, Parallel algorithm, parallel algorithms, Solver, diagonally dominant linear systems, Matrix (mathematics), Datavetenskap (datalogi), Narrow banded, Algorithm, Mathematics, Cyclic reduction, Diagonally dominant matrix
Abstract

ScaLAPACK contains a pair of routines for solving systems which are narrow banded and diagonally dominant by rows. Mathematically, the algorithm is block cyclic reduction. The ScaLAPACK implementation can be improved using incomplete, rather than complete block cyclic reduction. If the matrix is strictly dominant by rows, then the truncation error can be bounded directly in terms of the dominance factor and the size of the partitions. Our analysis includes new results applicable in our ongoing work of developing an efficient parallel solver.

Published
2012

14. Parallel solution of narrow banded diagonally dominant linear systems

Abstract

ScaLAPACK contains a pair of routines for solving systems which are narrow banded and diagonally dominant by rows. Mathematically, the algorithm is block cyclic reduction. The ScaLAPACK implementation can be improved using incomplete, rather than complete block cyclic reduction. If the matrix is strictly dominant by rows, then the truncation error can be bounded directly in terms of the dominance factor and the size of the partitions. Our analysis includes new results applicable in our ongoing work of developing an efficient parallel solver.

Published
2012
Full Text
View/download PDF

15. Parallel solution of narrow banded diagonally dominant linear systems

Abstract

ScaLAPACK contains a pair of routines for solving systems which are narrow banded and diagonally dominant by rows. Mathematically, the algorithm is block cyclic reduction. The ScaLAPACK implementation can be improved using incomplete, rather than complete block cyclic reduction. If the matrix is strictly dominant by rows, then the truncation error can be bounded directly in terms of the dominance factor and the size of the partitions. Our analysis includes new results applicable in our ongoing work of developing an efficient parallel solver.

Published
2012
Full Text
View/download PDF

16. Parallel solution of narrow banded diagonally dominant linear systems

Abstract

ScaLAPACK contains a pair of routines for solving systems which are narrow banded and diagonally dominant by rows. Mathematically, the algorithm is block cyclic reduction. The ScaLAPACK implementation can be improved using incomplete, rather than complete block cyclic reduction. If the matrix is strictly dominant by rows, then the truncation error can be bounded directly in terms of the dominance factor and the size of the partitions. Our analysis includes new results applicable in our ongoing work of developing an efficient parallel solver.

Published
2012
Full Text
View/download PDF

17. Parallel solution of narrow banded diagonally dominant linear systems

Abstract

ScaLAPACK contains a pair of routines for solving systems which are narrow banded and diagonally dominant by rows. Mathematically, the algorithm is block cyclic reduction. The ScaLAPACK implementation can be improved using incomplete, rather than complete block cyclic reduction. If the matrix is strictly dominant by rows, then the truncation error can be bounded directly in terms of the dominance factor and the size of the partitions. Our analysis includes new results applicable in our ongoing work of developing an efficient parallel solver.

Published
2012
Full Text
View/download PDF

18. Parallel solution of narrow banded diagonally dominant linear systems

Abstract

ScaLAPACK contains a pair of routines for solving systems which are narrow banded and diagonally dominant by rows. Mathematically, the algorithm is block cyclic reduction. The ScaLAPACK implementation can be improved using incomplete, rather than complete block cyclic reduction. If the matrix is strictly dominant by rows, then the truncation error can be bounded directly in terms of the dominance factor and the size of the partitions. Our analysis includes new results applicable in our ongoing work of developing an efficient parallel solver.

Published
2012
Full Text
View/download PDF

19. Calculation of Interference for a Porous Wall Wind Tunnel by the Method of Block Cyclic Reduction.

Abstract

The lift interference was calculated for a porous wall wind tunnel by a modified method of block cyclic reduction. This efficient, numerical method has indicated its accuracy by comparison with other available analytical and approximate solutions. A scheme is introduced to search for optimum wall configurations. The lift interference computed for an NACA 64-series finite airfoil in some optimum configurations has demonstrated the achievement of minimization of interference. The effect of test section length is also examined. (Author), Prepared in cooperation with ARO, Inc., Tullahoma, Tenn., Rept. no. ARO-PWT-TR-75-63.

Published
1975

Catalog

Books, media, physical & digital resources
See catalog results