Spelling suggestions: "subject:"1atrix eompression"" "subject:"1atrix dompression""
1 |
Wavelet based fast solution of boundary integral equationsHarbrecht, Helmut, Schneider, Reinhold 11 April 2006 (has links) (PDF)
This paper presents a wavelet Galerkin scheme for the fast solution of boundary integral equations. Wavelet Galerkin schemes employ appropriate wavelet bases for the discretization of boundary integral operators which yields quasi-sparse system matrices. These matrices can be compressed such that the complexity for solving a boundary integral equation scales linearly with the number of unknowns without compromising the accuracy of the underlying Galerkin scheme. Based on the wavelet Galerkin scheme we present also an adaptive algorithm. By numerical experiments we provide results which demonstrate the performance of our algorithm.
|
2 |
Fully Discrete Wavelet Galerkin SchemesHarbrecht, Helmut, Konik, Michael, Schneider, Reinhold 04 April 2006 (has links) (PDF)
The present paper is intended to give a survey of the developments of the wavelet Galerkin boundary element method. Using appropriate wavelet bases for the discretization of boundary integral operators yields numerically sparse system matrices. These system matrices can be compressed to O(N_j) nonzero matrix entries without loss of accuracy of the underlying Galerkin scheme. Herein, O(N_j) denotes the number of unknowns. As we show in the present paper, the assembly of the compressed system matrix can be performed within optimal complexity. By numerical experiments we provide examples which corroborate the theory.
|
3 |
Wavelets for the fast solution of boundary integral equationsHarbrecht, Helmut, Schneider, Reinhold 06 April 2006 (has links) (PDF)
This paper presents a wavelet Galerkin scheme for the fast solution of boundary integral equations. Wavelet Galerkin schemes employ appropriate wavelet bases for the discretization of boundary integral operators. This yields quasi-sparse system matrices which can be compressed to O(N_J) relevant matrix entries without compromising the accuracy of the underlying Galerkin scheme. Herein, O(N_J) denotes the number of unknowns. The assembly of the compressed system matrix can be performed in O(N_J) operations. Therefore, we arrive at an algorithm which solves boundary integral equations within optimal complexity. By numerical experiments we provide results which corroborate the theory.
|
4 |
Wavelet Galerkin Schemes for Boundary Integral Equations - Implementation and QuadratureHarbrecht, Helmut, Schneider, Reinhold 06 April 2006 (has links) (PDF)
In this paper we consider the fully discrete wavelet Galerkin scheme for the fast solution of boundary integral equations in three dimensions. It produces approximate solutions within discretization error accuracy offered by the underlying Galerkin method at a computational expense that stays proportional to the number of unknowns. We focus on implementational details of the scheme, in particular on numerical integration of relevant matrix coefficients. We illustrate the proposed algorithms by numerical results.
|
5 |
Hierarchical Matrix Operations on GPUsBoukaram, Wagih Halim 26 April 2020 (has links)
Large dense matrices are ubiquitous in scientific computing, arising from the
discretization of integral operators associated with elliptic pdes, Schur complement
methods, covariances in spatial statistics, kernel-based machine learning, and numerical optimization problems. Hierarchical matrices are an efficient way for storing the
dense matrices of very large dimension that appear in these and related settings. They
exploit the fact that the underlying matrices, while formally dense, are data sparse.
They have a structure consisting of blocks many of which can be well-approximated by
low rank factorizations. A hierarchical organization of the blocks avoids superlinear
growth in memory requirements to store n × n dense matrices in a scalable manner,
requiring O(n) units of storage with a constant depending on a representative rank k
for the low rank blocks. The asymptotically optimal storage requirement of the resulting hierarchical matrices is a critical advantage, particularly in extreme computing
environments, characterized by low memory per processing core. The challenge then
becomes to develop the parallel linear algebra operations that can be performed directly on this compressed representation. In this dissertation, I implement a set of
hierarchical basic linear algebra subroutines (HBLAS) optimized for GPUs, including
hierarchical matrix vector multiplication, orthogonalization, compression, low rank
updates, and matrix multiplication. I develop a library of open source batched kernel operations previously missing on GPUs for the high performance implementation
of the H2 operations, while relying wherever possible on existing open source and
vendor kernels to ride future improvements in the technology. Fast marshaling routines extract the batch operation data from an efficient representation of the trees
that compose the hierarchical matrices. The methods developed for GPUs extend to
CPUs using the same code base with simple abstractions around the batched routine
execution. To demonstrate the scalability of the hierarchical operations I implement
a distributed memory multi-GPU hierarchical matrix vector product that focuses on
reducing communication volume and hiding communication overhead and areas of low
GPU utilization using low priority streams. Two demonstrations involving Hessians
of inverse problems governed by pdes and space-fractional diffusion equations show
the effectiveness of the hierarchical operations in realistic applications.
|
6 |
Fully Discrete Wavelet Galerkin SchemesHarbrecht, Helmut, Konik, Michael, Schneider, Reinhold 04 April 2006 (has links)
The present paper is intended to give a survey of the developments of the wavelet Galerkin boundary element method. Using appropriate wavelet bases for the discretization of boundary integral operators yields numerically sparse system matrices. These system matrices can be compressed to O(N_j) nonzero matrix entries without loss of accuracy of the underlying Galerkin scheme. Herein, O(N_j) denotes the number of unknowns. As we show in the present paper, the assembly of the compressed system matrix can be performed within optimal complexity. By numerical experiments we provide examples which corroborate the theory.
|
7 |
Wavelets for the fast solution of boundary integral equationsHarbrecht, Helmut, Schneider, Reinhold 06 April 2006 (has links)
This paper presents a wavelet Galerkin scheme for the fast solution of boundary integral equations. Wavelet Galerkin schemes employ appropriate wavelet bases for the discretization of boundary integral operators. This yields quasi-sparse system matrices which can be compressed to O(N_J) relevant matrix entries without compromising the accuracy of the underlying Galerkin scheme. Herein, O(N_J) denotes the number of unknowns. The assembly of the compressed system matrix can be performed in O(N_J) operations. Therefore, we arrive at an algorithm which solves boundary integral equations within optimal complexity. By numerical experiments we provide results which corroborate the theory.
|
8 |
Wavelet based fast solution of boundary integral equationsHarbrecht, Helmut, Schneider, Reinhold 11 April 2006 (has links)
This paper presents a wavelet Galerkin scheme for the fast solution of boundary integral equations. Wavelet Galerkin schemes employ appropriate wavelet bases for the discretization of boundary integral operators which yields quasi-sparse system matrices. These matrices can be compressed such that the complexity for solving a boundary integral equation scales linearly with the number of unknowns without compromising the accuracy of the underlying Galerkin scheme. Based on the wavelet Galerkin scheme we present also an adaptive algorithm. By numerical experiments we provide results which demonstrate the performance of our algorithm.
|
9 |
Wavelet Galerkin Schemes for Boundary Integral Equations - Implementation and QuadratureHarbrecht, Helmut, Schneider, Reinhold 06 April 2006 (has links)
In this paper we consider the fully discrete wavelet Galerkin scheme for the fast solution of boundary integral equations in three dimensions. It produces approximate solutions within discretization error accuracy offered by the underlying Galerkin method at a computational expense that stays proportional to the number of unknowns. We focus on implementational details of the scheme, in particular on numerical integration of relevant matrix coefficients. We illustrate the proposed algorithms by numerical results.
|
10 |
Multilevel adaptive cross approximation and direct evaluation method for fast and accurate discretization of electromagnetic integral equationsTamayo Palau, José María 17 February 2011 (has links)
El Método de los Momentos (MoM) ha sido ampliamente utilizado en las últimas décadas para la discretización y la solución de las formulaciones de ecuación integral que aparecen en muchos problemas electromagnéticos de antenas y dispersión. Las más utilizadas de dichas formulaciones son la Ecuación Integral de Campo Eléctrico (EFIE), la Ecuación Integral de Campo Magnético (MFIE) y la Ecuación Integral de Campo Combinada (CFIE), que no es más que una combinación lineal de las dos anteriores.Las formulaciones MFIE y CFIE son válidas únicamente para objetos cerrados y necesitan tratar la integración de núcleos con singularidades de orden superior al de la EFIE. La falta de técnicas eficientes y precisas para el cálculo de dichas integrales singulares a llevado a imprecisiones en los resultados. Consecuentemente, su uso se ha visto restringido a propósitos puramente académicos, incluso cuando tienen una velocidad de convergencia muy superior cuando son resuelto iterativamente, debido a su excelente número de condicionamiento.En general, la principal desventaja del MoM es el alto coste de su construcción, almacenamiento y solución teniendo en cuenta que es inevitablemente un sistema denso, que crece con el tamaño eléctrico del objeto a analizar. Por tanto, un gran número de métodos han sido desarrollados para su compresión y solución. Sin embargo, muchos de ellos son absolutamente dependientes del núcleo de la ecuación integral, necesitando de una reformulación completa para cada núcleo, en caso de que sea posible.Esta tesis presenta nuevos enfoques o métodos para acelerar y incrementar la precisión de ecuaciones integrales discretizadas con el Método de los Momentos (MoM) en electromagnetismo computacional.En primer lugar, un nuevo método iterativo rápido, el Multilevel Adaptive Cross Approximation (MLACA), ha sido desarrollado para acelerar la solución del sistema lineal del MoM. En la búsqueda por un esquema de propósito general, el MLACA es un método independiente del núcleo de la ecuación integral y es puramente algebraico. Mejora simultáneamente la eficiencia y la compresión con respecto a su versión mono-nivel, el ACA, ya existente. Por tanto, representa una excelente alternativa para la solución del sistema del MoM de problemas electromagnéticos de gran escala.En segundo lugar, el Direct Evaluation Method, que ha provado ser la referencia principal en términos de eficiencia y precisión, es extendido para superar el cálculo del desafío que suponen las integrales hiper-singulares 4-D que aparecen en la formulación de Ecuación Integral de Campo Magnético (MFIE) así como en la de Ecuación Integral de Campo Combinada (CFIE). La máxima precisión asequible -precisión de máquina se obtiene en un tiempo más que razonable, sobrepasando a cualquier otra técnica existente en la bibliografía.En tercer lugar, las integrales hiper-singulares mencionadas anteriormente se convierten en casi-singulares cuando los elementos discretizados están muy próximo pero sin llegar a tocarse. Se muestra como las reglas de integración tradicionales tampoco convergen adecuadamente en este caso y se propone una posible solución, basada en reglas de integración más sofisticadas, como la Double Exponential y la Gauss-Laguerre.Finalmente, un esfuerzo en facilitar el uso de cualquier programa de simulación de antenas basado en el MoM ha llevado al desarrollo de un modelo matemático general de un puerto de excitación en el espacio discretizado. Con este nuevo modelo, ya no es necesaria la adaptación de los lados del mallado al puerto en cuestión. / The Method of Moments (MoM) has been widely used during the last decades for the discretization and the solution of integral equation formulations appearing in several electromagnetic antenna and scattering problems. The most utilized of these formulations are the Electric Field Integral Equation (EFIE), the Magnetic Field Integral Equation (MFIE) and the Combined Field Integral Equation (CFIE), which is a linear combination of the other two. The MFIE and CFIE formulations are only valid for closed objects and need to deal with the integration of singular kernels with singularities of higher order than the EFIE. The lack of efficient and accurate techniques for the computation of these singular integrals has led to inaccuracies in the results. Consequently, their use has been mainly restricted to academic purposes, even having a much better convergence rate when solved iteratively, due to their excellent conditioning number. In general, the main drawback of the MoM is the costly construction, storage and solution considering the unavoidable dense linear system, which grows with the electrical size of the object to analyze. Consequently, a wide range of fast methods have been developed for its compression and solution. Most of them, though, are absolutely dependent on the kernel of the integral equation, claiming for a complete re-formulation, if possible, for each new kernel. This thesis dissertation presents new approaches to accelerate or increase the accuracy of integral equations discretized by the Method of Moments (MoM) in computational electromagnetics. Firstly, a novel fast iterative solver, the Multilevel Adaptive Cross Approximation (MLACA), has been developed for accelerating the solution of the MoM linear system. In the quest for a general-purpose scheme, the MLACA is a method independent of the kernel of the integral equation and is purely algebraic. It improves both efficiency and compression rate with respect to the previously existing single-level version, the ACA. Therefore, it represents an excellent alternative for the solution of the MoM system of large-scale electromagnetic problems. Secondly, the direct evaluation method, which has proved to be the main reference in terms of efficiency and accuracy, is extended to overcome the computation of the challenging 4-D hyper-singular integrals arising in the Magnetic Field Integral Equation (MFIE) and Combined Field Integral Equation (CFIE) formulations. The maximum affordable accuracy --machine precision-- is obtained in a more than reasonable computation time, surpassing any other existing technique in the literature. Thirdly, the aforementioned hyper-singular integrals become near-singular when the discretized elements are very closely placed but not touching. It is shown how traditional integration rules fail to converge also in this case, and a possible solution based on more sophisticated integration rules, like the Double Exponential and the Gauss-Laguerre, is proposed. Finally, an effort to facilitate the usability of any antenna simulation software based on the MoM has led to the development of a general mathematical model of an excitation port in the discretized space. With this new model, it is no longer necessary to adapt the mesh edges to the port.
|
Page generated in 0.0683 seconds