Search

The linking-domain extraction (LDE) decomposition method is a new non-overlapping domain decomposition method for parallel circuit simulation. However, the original LDE method is inefficient in both the computational procedure and storage cost. In this work, a novel hierarchical LDE (H-LDE) method is proposed to further improve the LDE method, which leverages all the hidden features of LDE that are not exploited in the original work to perform a multi-level decomposition of power systems. The LDE-based matrix equation solution computation procedure is first proposed to eliminate the necessity of computing the entire matrix inversion, and then the multi-level computation structure is proposed for fast matrix inversion of the decomposed sub-matrices. The mathematical complexity of the H-LDE method is analyzed, which is used to derive the two principles for decomposing a power system. These principles can be applied on both parallel and sequential compute architecture. The 4-level LDE decomposition is applied on the IEEE 118-bus test power system and implemented in both sequential and parallel, which is used to verify the validity and efficiency of the proposed H-LDE decomposition method. The simulation results of various benchmark test power systems show that the proposed H-LDE method can achieve better performance than the classical LU factorization and sparse KLU method within a certain system scale.

Sparse LU factorization is one of the key building blocks of sparse direct solvers and often dominates the computing time of circuit simulation programs. Existing GPU-accelerated sparse LU factorization methods either offload relatively small dense matrix-matrix multiplications to GPU cores, or extract level-set information to parallelize elimination operations in each level. However, because of the insufficient parallelism, neither of the methods can saturate a large amount of compute units on modern GPUs.We in this paper propose a synchronization-free sparse LU factorization algorithm called SFLU. To saturate GPU cores, our method lets each thread block eliminate a column and runs all the thread blocks at the same time. Through communicating dependency information stored on global memory, all the thread blocks either busy wait to run or get updated by their previous columns. Because elimination of all the columns work concurrently, our method avoids any barrier synchronization and saturates GPU resources. By benchmarking over 1000 sparse matrices on an NVIDIA Titan RTX GPU, our SFLU outperforms SuperLU and GLU by a factor of on average 155.71 and 8.21 (up to 3585.62 and 252.66), respectively.

A geometric multigrid solver is tested as a field solver for Particle-in-Cell simulations. The convergence of the multigrid solver for different boundary conditions is verified. The iterative solver reuses the solution from the last timestep in order to decrease the number of iterations. An electron avalanche in argon gas is a test example for the method to check the performance in a self-consistent field simulation. Performance of multigrid method was compared with LU decomposition which seems to be a viable alternative even for moderate-sized problems.

A novel Hierarchical (H-) LU decomposition direct solution based on higher order basis function (HOBF) is presented to solve electromagnetic (EM) scattering from electrically large conducting targets. Due to the H-matrix structure, the H-LU fast direct solver can efficiently calculate the inverse of a moment-method matrix. By utilizing a high order geometrical modeling, a HOBF can be defined. Therefore, the number of unknowns can be greatly reduced to further expedite the computation. Numerical results demonstrate that compared with the low order modeling, the proposed method can significantly enhance the computational efficiency of electrically large EM scattering problems.

Sensitivity analysis is an important method for power system stability analysis to obtain weak points of the power grid fault. However, the speed of the traditional sensitivity calculation method cannot realize the function of rapid analysis of the power grid. In this paper, the batch sensitivity calculation is accelerated in parallel by the Graphics Processing Unit (GPU). Firstly, the overall parallelization scheme of batch sensitivity calculation on CPU+GPU heterogeneous platform is studied. Then, the GPU kernel functions such as batch Jacobi matrix generation and batch sparse linear systems (SLS) up-looking LU decomposition are designed in detail. Finally, the performance of the above GPU-accelerated sensitivity analysis algorithm was tested on five power system examples. The results show that the proposed algorithm achieves a speedup of 149 times on a 9241-bus system.

In this paper, we report the results obtained from the acceleration of multi-binary64-type multiple precision LU decomposition with Intel's Advanced Vector Extensions 2 (AVX2). We targeted double-double (DD), triple-double (TD), and quad-double (QD) precision arithmetic designed using certain types of error-free transformation (EFT) arithmetic. We implemented accelerated DD, TD, and QD precision addition and multiplication using SIMDized EFT functions with AVX2, which perform simultaneous computation using four binary64 numbers on the x86_64 computing environment, and with these, we were able to develop multiple-precision LU decomposition based on SIMDized matrix multiplication. Our LU decomposition is up to three times faster than the non-accelerated one.

In this paper, we propose a complex-valued joint eigenvalue decomposition(C-JEVD) algorithm based on LU de-composition and successive rotations. The proposed algorithm factorizes the matrix of eigenvectors into a lower-triangular matrix and an upper-triangular matrix, and update these two matrices using successive rotations. In each rotation, the elementary rotation matrix contains only one complex-valued parameter, which could be easily obtained via solving a cubic equation. Therefore, the proposed algorithm has low complexity. The proposed algorithm is compared with other C-JEVD methods through simulations.

A high-speed parallel decoding algorithm for erasure codes in the distributed storage system is proposed in this paper. Although erasure codes can tolerate multiple failures, single failures represent 99.75% of recoveries. So the decoding is optimized in only 1 failure first and then complex odd and even failure number situations to work with the same module but different parameters and operation flow. The algorithm is implemented in Verilog and synthesized with GF 12nm technology lib. In comparison to Gaussian elimination, LU factorization Elimination the proposed algorithm can have 55.7% to 67% speed reduction clearly have advantages.

We demonstrate an efficient and accelerated implementation of a parallel sparse depth reconstruction framework using compressed sensing (CS) techniques. Recent work suggests that CS can be split up into smaller sub problems. This allows us to efficiently pre-compute important components of the LU decomposition and subsequent linear algebra to solve a set of linear equations found in algorithms such as the alternating direction method of multipliers (ADMM). For comparison, a fully discrete least square reconstruction method is also presented.We also investigate how reduced precision is leveraged to reduce the number of logic units in field-programmable gate array (FPGA) implementations for such sparse imaging systems. We show that the amount of logic units, memory requirements and power consumption is reduced significantly by over 70% with minimal impact on the quality of reconstruction. This demonstrates the feasibility of novel high resolution, low power and high frame rate light detection and ranging (LiDAR) depth imagers based on sparse illumination.

The LU decomposition is an essential element used in many linear algebra applications. Furthermore, it is used in LINPACK to benchmark the performance of modern multi-core processor environments. These processors offer a large memory hierarchy including multiple registers and various levels of cache. Registers or L1 data cache are small in size but also very fast. The L2 or L3 cache memory is usually shared among other cores and larger but slower. For the LU decomposition, the latency of fetching data from the main memory to the registers to perform a calculation also depends on the input matrix's memory access pattern. Here, we look at the block factorization algorithm, where the LU decomposition performance depends on the performance of the matrix multiplication. In both cases, the LU decomposition and the matrix multiplication, such a matrix is traversed by three nested loops. In this paper, we propose to traverse such loops in an order defined by a space-filling curve. This traversal dramatically improves data locality and offers effective exploitation of the memory hierarchy. Besides the canonical (or line-by-line) access pattern, we demonstrate the traversal in Hilbert-, Peano and Morton order. Our extensive experiments show that the Morton order (or Z -order) and the inverse Morton order (or И-order) have a better runtime performance compared to the others.

A novel domain decomposition method based on Full Basis Function division (FBF-DDM) is proposed to analyze scattering problems from electrically large and complex perfect electric conductor (PEC) targets. Specially, the original model surface is divided into several open subdomains according to the distribution of basis functions, and it is not necessary to add artificial surface or buffer region between adjacent subdomains. Meanwhile, the single-layer toothed triangular mesh cells located on one side of the boundary line between adjacent subdomains is shared by these two adjacent subdomains to ensure the integrity of basis functions. For the purpose of improving the simulation accuracy, each subdomain is solved independently by using LU decomposition. Furthermore, the coupling between different subdomains is calculated in the manner of near field to avoid the storage of mutual impedance matrix, and thus, the memory requirement is reduced greatly. Numerical results demonstrate the validity and the stability of the proposed method.

Expanded-Blaum-Roth (EBR) code encodes a (p – 1) × k information array into a p × p array such that any bit in a column can be recovered within the column and any k out of p columns can retrieve all (p – 1) × k information bits, where p is a prime number. In this paper, we generalize the construction of EBR code with a more flexible parameter, i.e., the number of bits stored in a column in the proposed construction can be not only a prime number but also an even number. In addition, we present an efficient encoding/decoding method for the proposed generalized EBR codes based on the LU factorization of Vandermonde matrix. We show that the proposed encoding/decoding method has less computational complexity than the existing method. Moreover, we show that the minimum symbol distance of generalized EBR codes is the same as that of EBR code for some parameters.

International audience; This paper adresses static resource allocation problems for irregular distributed parallel applications. More precisely, we focus on two classical tiled linear algebra kernels: the Matrix Multiplication (MM) and the LU decomposition (LU) algorithms on large linear systems. In the context of parallel distributed platforms, data exchanges can dramatically degrade the performance of linear algebra kernels and in this context, compression techniques such as Block Low Rank (BLR) compression techniques are good candidates both for limiting data storage on each processor and data exchanges between processors. On the other hand, the use of BLR representation makes the static allocation problem of tiles to processors more complex. Indeed, the load associated to each tile depends on its compression factor, which induces an heterogeneous load balancing problem. In turn, solving this load balancing problem optimally might lead to complex allocation schemes, where the tiles allocated to a given processor are scattered all over the matrix. This in turn induces communication costs, since matrix multiplication and LU decompositions heavily rely on broadcasting operations along rows and columns of processors, so that the communication volume is minimized when the maximal number of different processors on any row and column is minimized. In the fully homogeneous case, 2D Block Cyclic (BC) allocation solves both load balancing and communication minimization issues simultaneously , but it might lead to bad load balancing in the heterogeneous case. Our goal in this paper is to propose data allocation schemes dedicated to BLR format and to prove that it is possible to obtain good performance on makespan when simultaneously balancing the load and minimizing the maximal number of different processor in any row or column.

As an effective data dimensionality reduction technique, PCA is widely used in the field of process monitoring. PCR, as an improved method of PCA, obtains the coefficient matrix between input and output by least square regression of score matrix and quality variable. However, the detection effect of PCR on quality-related faults still needs to be improved. Focusing on this issue, a MPCR method for quality-related fault detection is proposed in this paper. Where LU decomposition is introduced to further decompose the coefficient matrix of PCR, decompose process variables into quality-related and quality-independent parts, and design corresponding test statistics to make the algorithm more suitable for modern industrial systems. The effectiveness of the algorithm is verified by a numerical example and the Tennessee Eastman process. The results show that MPCR algorithm has higher fault detection rate and better tracking performance than the traditional PLS.

Getting performance on high-end heterogeneous nodes is challenging. This is due to the large semantic gap between a computation's specification-possibly mathematical formulas or an abstract sequential algorithm-and its parallel implementation; this gap obscures the program's parallel structures and how it gains or loses performance. We present Hedgehog, a library aimed at coarse-grain parallelism. It explicitly embeds a dataflow graph in a program and uses this graph at runtime to drive the program's execution so it takes advantage of hardware parallelism (multicore CPUs and multiple accelerators). Hedgehog has asynchronicity built in. It statically binds individual threads to graph nodes, which are ready to fire when any of their inputs are available. This allows Hedgehog to avoid using a global scheduler and the loss of performance associated with global synchronizations and managing of thread pools. Hedgehog provides a separation of concerns and distinguishes between compute and state maintenance tasks. Its API reflects this separation and allows a developer to gain a better understanding of performance when executing the graph. Hedgehog is implemented as a C++ 17 headers-only library. One feature of the framework is its low overhead; it transfers control of data between two nodes in ≈ 1 µs. This low overhead combines with Hedgehog's API to provide essentially cost-free profiling of the graph, thereby enabling experimentation for performance, which enhances a developer's insight into a program's performance. Hedgehog's asynchronous data-flow graph supports a data streaming programming model both within and between graphs. We demonstrate the effectiveness of this approach by highlighting the performance of streaming implementations of two numerical linear algebra routines, which are comparable to existing libraries: matrix multiplication achieves >95 % of the theoretical peak of 4 GPUs; LU decomposition with partial pivoting starts streaming partial final result blocks 40 5 earlier than waiting for the full result. The relative ease and understandability of obtaining performance with Hedgehog promises to enable non-specialists to target performance on high-end single nodes.

This article provides two new features that in combinations facilitate the construction of a transfer function in RC and RL circuits, and in s-expanded polynomials. First is the introduction of tuple-based array manipulations, where multiplications and divisions are replaced with convolutions and deconvolutions, respectively. Second, it introduces a new UaL decomposition for tuple-based matrices. The UaL decomposition is proven to be computationally more efficient compared to the traditional LU factorization. It is shown that the growth of the entries in both U and L matrices are gradual and follow a geometrical pattern, as the decomposition progresses. Another important feature of the UaL decomposition is that it does not generate nonzero remainders, or simply, it is “cancellation free”. The method is applied to the MNA representation of an RC (or RL) circuit. Finally, it is shown that working in the tuple-based format puts the U and L matrix entries into s-expanded form, such as P(s) = a n sn + a n-1 sn-1 +…+ a 0 , which in turn produces s-expanded transfer functions.

Even though analog computation is better suited for differential equation solutions (ODE, PDE), sometimes it needs to solve systems of linear equations. This discussion focuses on analog solutions of linear equation systems, implemented on a configurable platform. Digital systems rely on solving linear equations as the fundamental numerical computation. Systems of linear equations are used to solve static circuits illustrating that at least a reduced class of analog physical linear system computation should be possible. The analog approaches utilize iterative techniques, setting up a set of ODEs to solve the system of linear equations, rather than relying on matrix decompositions (e.g. LU decomposition). The approach allows for multiple potential configurable circuit approaches. A set of amplifier networks has been designed to demonstrate the solutions for different matrices. These techniques provide energy-efficient continuous-time solutions. The resulting algorithm has been studied considering the analog numerical analysis for the solution and convergence time.

Large linear systems are used in many applications, and millions of equations can be utilized (e.g., in aircraft manufacturing). These equations need to be simplified, which allows faster processing and easier implementation. The LU decomposition method and its pipelined version are implemented to illustrate their efficiency. A comprehensive comparison between the sequential LU decomposition, multithreading LU decomposition, and TPL methods is conducted under different coefficient matrix block sizes to represent these systems. The results show that the multithreading and TPL approaches reduce the processing time required to compute the coefficient matrix compared to sequential processing. This finding will help improve the performance of some techniques in the literature by paralyzing the LU decomposition part of the system.

Fuzzy theory and linear algebra have a substantial role in various sciences and the biggest effect was in the share of computer science. In the field of image processing, the process of digital image watermarking represents the inclusion of a secret logo or an image called watermark into a host image to get a watermarked image to guarantee copyright protection or ownership. The watermarking will be acceptable if it achieves specific qualities like imperceptibility and robustness. In this paper, Mamdani fuzzy inference system (FIS) was employed on the original image for obtaining the controller parameter which works on finding a trade-off between imperceptibility and robustness, and on the other hand, is combined with the algebraic matrix decomposition method LU for proposing a digital watermarking technique in which the watermark is included in the LH2 band produced by applying two-level of the lifting wavelet transform (LWT) using the modular arithmetic (mod). The experimental results show that the proposed algorithm resistant to many attacks.

Given the Nodal Admittance Matrix (NAM) of a linear circuit this article provides means to generate any desired transfer function, or s-expanded polynomial, in a very efficient way. There are three features that are used in combinations to facilitate this task. The first feature is the use of the state space and characteristic equation. The second feature is tuple-based array manipulations. In these manipulations multiplications and divisions are replaced with convolutions and deconvolutions. The last feature to work with is the newly developed UaL decomposition for tuple-based matrices [7]. The UaL decomposition is proven to be computationally more efficient compared to the traditional LU factorization. It is shown that the growth of the entries in both $U$ and $L$ matrices are gradual and it follow a geometrical pattern as the decomposition progresses. Another important feature of the UaL decomposition is that it does not generate nonzero remainders, or simply, it is an “error free” procedure. The method is applied to the Branch Admittance Matrix (BAM) representation of an RC (or RL) circuit. Finally, it is shown that working in the tuple-based format puts the $U$ and $L$ matrix entries into s-expanded form, such as $P(s)=a_{n}s^{n}+a_{n-1}s^{n-I}+\ldots+a_{0}$ , which in turn produces $s$ -expanded transfer functions.

Binary maximum distance separable (MDS) array codes are an important class of MDS codes with low computational complexity, as only XOR operations are involved in the encoding/decoding procedures. Most existing binary MDS array codes are constructed based on Vandermonde matrix or Cauchy matrix, as we have efficient decoding methods for Vandermonde and Cauchy linear systems. We call the array codes with encoding matrix being Vandermonde matrix and Cauchy matrix as Vandermonde MDS array codes and Cauchy MDS array codes, respectively. In this paper, we implement Vandermonde MDS array codes and Cauchy MDS array codes, and evaluate their encoding and decoding performance. Our implemented results show that Vandermonde MDS array codes have better encoding/decoding performance than that of Cauchy MDS array codes. Specifically, the encoding rate of Vandermonde MDS array codes is about 58% higher than that of Cauchy MDS array codes, and the decoding rate of Vandermonde MDS array codes is about 70% higher than that of Cauchy MDS array codes. In our implementation, the efficient decoding method is based on the LU factorization of Vandermonde matrix and Cauchy matrix. Thus, only some pattern of the decoding procedure of Vandermonde MDS array codes is considered in this paper.

Much of the recent work on domain-specific architectures has focused on bridging the gap between performance/efficiency and programmability. We consider one such example architecture, Transformer, consisting of light-weight cores interconnected by caches and crossbars that supports run-time reconfiguration between shared and private cache mode operations. We present customized implementation of a select set of linear algebra kernels, namely, triangular matrix solver, LU decomposition, QR decomposition and matrix in-version, on Transformer. The performance of the kernel algorithms is evaluated with respect to execution time and energy efficiency. Our study shows that each kernel achieves high performance for a certain cache mode and that this cache mode can change when the matrix size changes, making a case for run-time reconfiguration.

In this paper, we describe and evaluate an extension of the Chameleon library to operate with hierarchical matrices (H-Matrices) and hierarchical arithmetic (H-Arithmetic), producing efficient solvers for linear systems arising in Boundary Element Methods (BEM). Our approach builds upon an open-source H-Matrices library from Airbus, named Hmat-oss, that collects sequential numerical kernels for both hierarchical and low-rank structures; the tiled algorithms and task-parallel decompositions available in Chameleon for the solution of linear systems; and the StarPU runtime system to orchestrate an efficient task-parallel (multi-threaded) execution on a multicore architecture. Using an application producing matrices with features close to real industrial applications, we present shared-memory results that demonstrate a fair level of performance, close to (and sometimes better than) the one offered by a pure H-Matrix approach, as proposed by Airbus Hmat proprietary (and non open-source) library. Hence, this combination Chameleon + Hmat-oss proposes the most efficient fully open-source software stack to solve dense compressible linear systems on shared memory architectures (distributed memory is under development).

It is well known that solving a sparse system of linear equations is the workhorse critical step in analog and RF circuit simulation. The LU factorization of sparse system matrix is a key operation in order to solve a system of linear equations. Extracting parallelism to factorize a sparse matrix requires knowledge of pattern of non-zeros in the matrix. Exploiting the fact that sparsity patterns of matrices involved in circuit simulations do not change across iterations, the schedule of computing steps of LU factorization can be statically determined and analyzed for parallelism. This approach has been well investigated by [1] and [2] in recent years. Our work improvises this well-researched approach and exposes more parallelism, thereby yielding improved results (by factor up to 2). The accelerated design is prototyped using custom high-level-synthesis tool specific to LU decomposition problem.The case of RF Circuits is treated slightly differently. Such circuits have a number of nonlinear components. Periodic steady state response can be determined efficiently using Harmonic Balance method even when amplitudes are not small. Acceleration of this method has been a subject of vigorous interest in recent years [4], [7]. The system matrix appearing in this method is a sparse set of tiles whose solution can benefit from the techniques mentioned above. The sparsity pattern is inherited from the circuit connections. This paper describes FPGA-and manycore-based acceleration of automated Harmonic Balance (HB) simulator which simulates a circuit with a netlist similar to SPICE. Our 100MHz custom digital design on the FPGA of ZedBoard (XC7Z020) yields a speed up of up to 4.39 over the on-chip dual Core ARM Cortex-A9, 666 MHz processor. And on Intel’s Xeon Phi Knights Landing (KNL) manycore chip, we obtain a speed up of up to 8.96 over a 4-core Intel i7 processor running at 3GHz clock frequency.

To fully leverage the emerging non-volatile main memory (NVMM) for high-performance computing, programmers need efficient data structures that are aware of NVMM memory models and provide crash consistency. Manual creation of NVMM-aware persistent data structures requires a deep understanding of how to create persistent snapshots of memory objects corresponding to the data structures and substantial code modification, which makes it very difficult to use in its manual form even for experienced programmers. To simplify the process, we design a compiler-assistant technique, NVPath. With the aid of compilers, it automatically generates NVMM-aware persistent data structures that provide the same level of guarantee of crash consistency compared to the baseline code. Compiler-assistant code annotation and transformation are general and can be applied to applications using various data structures. Furthermore, it is a gray-box technique which requires minimum users’ input. Finally, it keeps the baseline code structure for good readability and maintenance. Our experimental results with real-world scientific applications (e.g., matrix multiplication, LU decomposition, adaptive-mesh refinement, and page ranking) show that the performance of annotated programs is commensurate with the version using the manual code transformation on the Titan supercomputer.

To minimize data movement, many parallel ap- plications statically distribute computational tasks among the processes. However, modern simulations often encounters ir- regular computational tasks whose computational loads change dynamically at runtime or are data dependent. As a result, load imbalance among the processes at each step of simulation is a natural situation that must be dealt with at the programming level. The de facto parallel programming approach, flat MPI (one process per core), is hardly suitable to manage the lack of balance, imposing significant idle time on the simulation as processes have to wait for the slowest process at each step of simulation. One critical application for many domains is the LU factor- ization of a large dense matrix stored in the Block Low-Rank (BLR) format. Using the low-rank format can significantly reduce the cost of factorization in many scientific applications, including the boundary element analysis of electrostatic field. However, the partitioning of the matrix based on underlying geometry leads to different sizes of the matrix blocks whose numerical ranks change at each step of factorization, leading to the load imbalance among the processes at each step of factorization. We use BLR LU factorization as a test case to study the programmability and performance of five different programming approaches: (1) flat MPI, (2) Adaptive MPI (Charm++), (3) MPI + OpenMP, (4) parameterized task graph (PTG), and (5) dynamic task discovery (DTD). The last two versions use a task-based paradigm to express the algorithm; we rely on the PaRSEC run- time system to execute the tasks. We first point out programming features needed to efficiently solve this category of problems, hinting at possible alternatives to the MPI+X programming paradigm. We then evaluate the programmability of the different approaches, detailing our experience implementing the algorithm using each of the models. Finally, we show the performance result on the Intel Haswell–based Bridges system at the Pittsburgh Supercomputing Center (PSC) and analyze the effectiveness of the implementations to address the load imbalance.

An approach for reducing the vector FEM curlcurl matrix bandwidth in 2D magnetostatics is propsed. In the tree cotree method, the cotree edges are chosen so that the resulting curl-curl matrix bandwith stays as close to the main diagonal as possible. It is shown that it is possible to obtain a tridiagonal matrix in the case of rectangular elements. In the case of triangular elements it is possible to obtain a curl-curl matrix that is very close to a tridiagonal one. An advantage of direct LU decomposition over the iterative method is shown.

As the foundation of planning and operation, hybrid energy flow analysis of integrated energy system is of significance. To improve the computational efficiency, this paper proposes a hybrid energy flow calculation method for electric-thermal coupling systems based on a parallelized Inexact Newton method. The proposed method uses an iterative method to solve the modified equations during energy flow calculations. By selecting reasonable iterative algorithm, precondition method and iterative convergence criterion, it can effectively improve the efficiency of energy flow calculations and facilitate parallelization calculations. In this paper, we consider the asymmetric positive definiteness characteristics of the Jacobian matrix during energy flow calculation. The generalized minimization residual method (GMRES) is chosen as the internal iterative algorithm of the Inexact Newton method, and the incomplete LU decomposition method (ILU) is proposed as the precondition method to accelerate the internal iterative convergence speed. The constant forcing factor is used as the internal convergence criterion. The algorithm is designed with GPU parallelization. Finally, the effectiveness of the proposed method is verified by extensive case studies.

An efficient parallel direct solver with a new pivoting scheme is presented for solving impedance matrix equations generated by the higher-order method of moments in high-frequency electromagnetic computation. Given the diagonal dominance characteristic of the dense complex impedance matrices, a local-block pivoted parallel LU decomposition algorithm is developed in the solver, which requires less communication time than the Intel math kernel library and the communication avoiding LU solver, because the pivoting operations execute in local blocks of the processes. To demonstrate the stability and performance of the algorithm, electromagnetic radiation and scattering from complex models containing metallic and dielectric structures are computed. When up to 1200 CPU cores are used, numerical results show that the solving time of the proposed LU solver is significantly reduced.

Data mining is an important task to understand the valuable information for making right decision. There are numerous mature technologies for mining self-owned data of a party. However, how to perform distributed data mining to obtain information from data owned by multi-party without privacy leak is still a challenge. In recent years, secure multi-party computation (MPC) shows its potential capability for solving this problem. Meanwhile, there are a number of problems to be solved before utilizing in business environment. In this paper, we point out two unsupported tasks of MPC that are common in real-world. Towards this end, we design algorithms based on optimized matrix computation with one-hot encoding and LU decomposition to support these in MPC context requirements. In addition, we implement them based on a SPDZ protocol, a computation framework of MPC. The experimental evaluation results demonstrate that our design and implementation are feasible and effective for privacy preserving distributed data mining.

Parallelizing the LU factorization of sparse Jacobian matrices reduces the execution time of the power flow algorithm which aids in real time control of the power system. In this paper, acceleration of LU factorization by employing different Graphical Processing Units(GPUs) is discussed. The hybrid column based right-looking LU factorization algorithm is found to be more amenable for GPU implementation. The structural symmetry property of non-zeros in the matrix is exploited to maximize the column/node level parallelization through a matrix re-ordering scheme obtained from Jess-Kees' algorithm. Also the influence of different fill-in reducing matrix re-orderings in the context of parallelization and execution time is discussed. The proposed method is tested on a set of power flow Jacobians with dimensions ranging from 4438 to 1136128 on different GPUs. Results from the current work demonstrate scalability of the proposed method with progressively powerful GPUs yielding better execution times. Efficacy of the proposed method is corroborated by improved speedup in execution when compared with CPU-based serial sparse system solvers like UMFPACK and KLU.

Sparse matrix LU factorization is one of the core modules in power system simulation tools. This paper deals with the usage of Graphical Processing Unit(GPU) for accelerating LU factorization. Out of the many methods found in literature, the hybrid column based right-looking LU factorization is considered to be better in terms of parallelization. The column/node level concurrency available in the hybrid column based right looking factorization algorithm is enhanced by utilizing the structural symmetry property of non-zeros in the Jacobian. Jess-Kees' algorithm is employed to obtain a matrix re-ordering scheme, which maximizes parallelism. The proposed method is tested on Jacobians of varying dimensions occurring in the power flow problem on a NVIDIA Quadro P5000 GPU. Significant speedups are obtained over CPU-based serial sparse system solvers like UMFPACK and KLU, demonstrating the effectiveness of the proposed methodology.

This paper presents a progressive approach for optimizing the batched LU factorization on graphics processing units (GPUs). The paper shows that the reliance on level-3 BLAS routines for performance does not really pay off, and that it is indeed important to pay attention to the memory-bound part of the algorithm, especially when the problem size is very small. In this context, we develop a size-aware multi-level blocking technique that utilizes different granularities for kernel fusion according to the problem size. Our experiments, which are conducted on a Tesla V100 GPU, show that the multi-level blocking technique achieves speedups for single/double precisions that are up to 3.28×/2.69× against the generic LAPACK-style implementation. It is also up to 8.72×/7.2× faster than the cuBLAS library for single and double precisions, respectively. The developed solution is integrated into the open-source MAGMA library.

The emergence of deep learning as a leading computational workload for machine learning tasks on large-scale cloud infrastructure installations has led to plethora of accelerator hardware releases. However, the reduced precision and range of the floating-point numbers on these new platforms makes it a non-trivial task to leverage these unprecedented advances in computational power for numerical linear algebra operations that come with a guarantee of robust error bounds. In order to address these concerns, we present a number of strategies that can be used to increase the accuracy of limited-precision iterative refinement. By limited precision, we mean 16-bit floating-point formats implemented in modern hardware accelerators and are not necessarily compliant with the IEEE half-precision specification. We include the explanation of a broader context and connections to established IEEE floating-point standards and existing high-performance computing (HPC) benchmarks. We also present a new formulation of LU factorization that we call signed square root LU which produces more numerically balanced L and U factors which directly address the problems of limited range of the low-precision storage formats. The experimental results indicate that it is possible to recover substantial amounts of the accuracy in the system solution that would otherwise be lost. Previously, this could only be achieved by using iterative refinement based on single-precision floating-point arithmetic. The discussion will also explore the numerical stability issues that are important for robust linear solvers on these new hardware platforms.

In this paper, we present a novel skeletonization based fast direct solver for analyzing electromagnetic scattering from electrically conducting objects. The contributions of the present algorithm involve two aspects: reducing the cost for filling proxy matrices and enhancing the inverse process. To reduce the filling time of proxy matrices, the proxy surface is discretized by a series of points. The number of the points is considerably small compared with conventional method. Consequently, the dimensions of the proxy matrices for each group can be reduced remarkably in this way. On the other hand, a multiplicative factorization technique, recursive skeletonization factorization, is utilized in the inverse process. The projection matrices obtained by interpolative decomposition can be used directly with high efficiency. The remained block diagonal matrices after factorization can be easily solved by LU decomposition. The accuracy and efficiency of the proposed method will be validated by numerical results.

In many scientific computations, Lower-upper (LU) decomposition is an important computing step, as most of the scientific applications are modeled using linear equations Ax=b. The Linear equations are used in our everyday life applications such as profit prediction in the business, income over time, mileage rate calculation. The complexity of data makes difficult to parallelize the LU decomposition. Because parallelization of LU decomposition improves the speed of solving LU factorization and reduces the delay in critical applications range from weather forecasting to power system problems-load flow computation. Field Programmable Gate Array (FPGA) is having more logic resources and parallel computing to speed up the matrix decomposition. In this work an area efficient High Throughput Architecture is designed for Sparse Matrix LU factorization by changing/modifying the computing steps in algorithm. The problem with the KLU algorithm is it occupies more area and the throughput is less when compared with the modified KLU algorithm. The area is reduced by the 10%. The hardware complexity of implementation of sparse LU Factorization on FPGA is 15% less when compared with CPU & GPU [4] and also the computing efficiency i.e., throughput 10% to 12% on GPU&CPU do not reach theoretical computing efficiency (theoretical peak throughput).The hardware efficiency (typically 1 to 4%) of UMFPACK and SuperLU, are very less due to poor utilization of Floating point.

Acceleration of in-core LU decomposition of a dense MoM matrix by using multiple GPUs in parallel, is presented in this paper. Results for nonsymmetrical and symmetrical matrices are shown. Limitations for further increasing the parallelization efficiency and the ways for overcoming these limitations are discussed. The achieved acceleration efficiency is high (about 65%), but remains limited by the speed of data transfers between CPU RAM and GPUs VRAM.

We propose a scalable, and memory and time efficient parallel blockwise-sparse LU decomposition for distributed NUMA architectures suitable for global domain decomposition preconditioning. A static task scheduling heuristic is used to spatial and temporary allocate computational tasks on distributed NUMA systems. Asynchronous communication aided by manual progression techniques are used to maximize communication and computation overlap. Comparisons with state of the art sparse direct solvers on various electrically large problems suggest up to 2 times less memory and up to 4 times faster time while having better parallel efficiency.

B-Spline is an approximating curve, its shape is determined by the control points but it also has parametric nature. To interpolate data points, various works have been done by the previous researcher in B-Spline parameterization. The proposed study is the extension in the B-spline interpolation technique using arbitrary end derivatives. In this paper, we present a new way for interpolating cubic B-Spline curve by taking first and second derivative at endpoints and only first derivative at inner points. An algorithm is presented for interpolating data points. The algorithm computes knot values for parameterization methods. These knot values are used in constructing a matrix of B-Spline basis function and derivative of the basis function. Then, we solved it for unknown control points by using the LU decomposition method, such that the curve will pass through the original data points. For interpolation, the parameterization method used in this paper is exponential parameterization. The main advantage of this concept of derivatives is that we can generate different shapes of curves by setting different direction at all points. As an application, our method is applied in a curve reconstruction on road map with data points and driving directions.

This paper presents a comparative analysis of three LU decomposition methods – KLU, NICSLU, and GLU – focusing on their performance when applied on power system simulation problems. This assessment is performed via experimental results of the execution times. The data sample for these experiments is composed of individual benchmark matrices as well as complete simulations which are representative for RTE’s phasor time domain simulations. The NICSLU method yields encouraging results, especially for refactorization, which opens up prospects for performance improvements, both on current solving methods and on alternative numerical computation schemes that could thus update the Jacobian more frequently to avoid several residual function evaluations and decrease the overall computation time.

Medical technology has developed rapidly in recent years, the problem of medical misdiagnosis causing by the breezing medical images has not been solved effectively. Especially because of the low resolution of the original image(x-ray image) and some external factors (such as light and electricity), it is hard to distinguish the specific parts (such as lung) of the human body with minor difference in gray-scale. In this paper, we propose an algorithm for medical images based on LU decomposition. The experimental results indicate that there is a clear difference between the two processed U matrices, that have different distributions of black and white points. The research results are useful to observe the minor difference in medical images (such as X-ray images and CT images), which can help doctors diagnose and track disease and avoid the misdiagnosis caused by the fuzzy small parts of the image as much as possible.