Search

Previous algorithms for decoding AG codes up to the designed distance all assumed existence of an extra rational place on the base algebraic curve. The place is used to solve the decoding problem by linear algebra over the base field of the curve. The rationality of the place is essential, and therefore AG codes supported by all rational places on the curve are excluded from the domain of applicability of the decoding algorithms. This paper presents a decoding algorithm for those AG codes using an extra place of higher degree. Hence finally all AG codes, as Goppa defined 40 years ago, are equipped with a fast decoding algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we consider the precoder design for an underloaded or critically loaded downlink multi-user multiple-input multiple-output (MIMO) communication system. We propose novel precoding and decoding schemes which enhance system performance based on rate splitting at the transmitter and single-stage successive interference cancellation at the receivers. The proposed successive null-space (SNS) precoding utilizes linear combinations of the null-space basis vectors of the successively augmented MIMO channel matrices of the users as precoding vectors to adjust the inter-user-interference experienced by the receivers. We formulate a non-convex weighted sum rate optimization problem for the precoding vectors and the associated power allocation for the proposed SNS-based MIMO-rate-splitting multiple access (RSMA) scheme. We obtain a suboptimal solution for this problem via successive convex approximation. Moreover, we study the robustness of the proposed precoding scheme to imperfect channel state information (CSI) at the base station via derivative-based sensitivity analysis. Our analysis and simulation results reveal the enhanced performance and robustness of the proposed SNS-based MIMO-RSMA scheme over several baseline multi-user MIMO schemes, especially for imperfect CSI. [ABSTRACT FROM AUTHOR]

Federated learning (FL) is a privacy-aware data mining strategy keeping the private data on the owners’ machine and thereby confidential. The clients compute local models and send them to an aggregator which computes a global model. In hybrid FL, the local parameters are additionally masked using secure aggregation, such that only the global aggregated statistics become available in clear text, not the client specific updates. In this context, we investigate the data leakage of three popular algorithms for QR decomposition, Gram-Schmidt orthonormalization, the Householder algorithm and Givens rotation. We show that, even when using additive SMPC, Givens rotation and the Householder matrix leak raw data and are therefore not suited for this computation paradigm. Gram-Schmidt orthonormalization relies on inner vector products and does not leak raw data points. [ABSTRACT FROM AUTHOR]

Many graph-based algorithms in high performance computing (HPC) use approximate solutions due to having algorithms that are computationally expensive or serial in nature. Neural acceleration, i.e., the process of speeding up approximation computation elements via artificial neural networks, is relatively new and has not focused on HPC graph-based algorithms. In this paper, we propose a starting point for applying models for neural acceleration to graph-based HPC algorithms utilizing an understanding of the connectivity computational pattern, recursive neural networks, and graph neural networks. We demonstrate these techniques on the problem related to the utility functions of sparse matrix ordering and fill-in (i.e., zero elements becoming nonzero during factorization) calculations. The problem of sparse matrix ordering is commonly used for issues related to load balancing, improving memory reuse, or reducing computational and memory costs in direct sparse linear solver methods. These utility functions are ideal for demonstration as they comprise a number of different graph-based subproblems, and thus demonstrate the usefulness of our method over a wide range. We show that we can accurately approximate the best ordering and the nonzero count of the sparse factorization matrix while speeding up the calculation by as much as $30.3\times $ over the traditional serial method.

In power electronics, diode rectifiers are often regarded as the counterpart of a power amplifier. That is plausible because a power amplifier converts dc energy into RF, and a rectifier works in the reverse. In fact, wireless power transfer systems employ a power amplifier for transmission and a diode rectifier for reception. Therefore, the design theory of rectifiers is supposed to be analogous to that of power amplifiers. Is it straightforward to adapt the amplifier theory for rectifiers? [ABSTRACT FROM AUTHOR]

The matrix-multiply assist (MMA) facility is the latest addition to IBM's power instruction set architecture and first shipped in the recently introduced POWER10 processor. MMA is designed to accelerate matrix–matrix operations, such as matrix multiplication and convolution, using instructions that compute the outer product of vector-register operands. Outer product computations have been used for decades in linear algebra libraries to deliver high-performance implementations of matrix operations. Such libraries use conventional single-instruction–multiple-data (SIMD) instructions to emulate outer product operations. MMA in POWER10 is the first hardware with direct support for outer product operations released in the market. MMA operates with the widest diversity of data types compared to any accelerator design currently announced. Unleashing the high-performance enabled by MMA requires careful code generation. Two key considerations for optimal MMA code performance are 1) the choice of accumulation layout when maximizing the using the accumulators and 2) the selection of matrix access order. This article shows that over 92% of peak performance in POWER10 with MMA can be achieved when the code generation makes the right choices. [ABSTRACT FROM AUTHOR]

Computation in several real-world applications such as probabilistic machine learning, sparse linear algebra, and robotic navigation can be modeled as irregular directed acyclic graphs (DAGs). The irregular data dependencies in DAGs pose challenges to parallel execution on general-purpose CPUs and GPUs, resulting in severe under-utilization of the hardware. This article proposes DAG Processing Unit (DPU), a specialized processor designed for the efficient execution of irregular DAGs. The DPU is equipped with parallel compute units (CUs) that execute different subgraphs of a DAG independently. The CUs can synchronize within a cycle using a hardware-supported synchronization primitive and communicate via an efficient interconnect to a global banked scratchpad. Furthermore, a precision-scalable positTrademarked. arithmetic unit is developed to enable application-dependent precision. The DPU is taped out in 28-nm CMOS, achieving a speedup of 5.1 $\times $ and 20.6 $\times $ over state-of-the-art CPU and GPU implementations on DAGs of sparse linear algebra and probabilistic machine learning workloads. This performance is achieved while operating at a power budget of 0.23 W, as opposed to 55 and 98 W of the CPU and GPU, resulting in a peak efficiency of 538 GOPS/W with DPU, which is 1350 $\times $ and 9000 $\times $ higher than the CPU and GPU, respectively. Thus, with specialized architecture, DPU enables low-power execution of irregular DAG workloads. [ABSTRACT FROM AUTHOR]

This article is dedicated to Jack Dongarra on the occasion of him receiving the 2021 ACM Turing Award and concentrates primarily on his contributions to numerical linear algebra, particularly on the development of algorithms and software to reliably and efficiently solve linear algebra problems. We shall look at software projects, a number of them initiated by Jack, ranging from the BLAS and LINPACK through LAPACK to recent projects, such as SLATE, as well as some of his algorithmic contributions. Quoting from one of Jack's own recent talks, his tenets have been "accuracy, community, innovation, performance, portability, productivity, readability, and reliability." [ABSTRACT FROM AUTHOR]

Thomson’s multitaper method estimates the power spectrum of a signal from $N$ equally spaced samples by averaging $K$ tapered periodograms. Discrete prolate spheroidal sequences (DPSS) are used as tapers since they provide excellent protection against spectral leakage. Thomson’s multitaper method is widely used in applications, but most of the existing theory is qualitative or asymptotic. Furthermore, many practitioners use a DPSS bandwidth $W$ and number of tapers that are smaller than what the theory suggests is optimal because the computational requirements increase with the number of tapers. We revisit Thomson’s multitaper method from a linear algebra perspective involving subspace projections. This provides additional insight and helps us establish nonasymptotic bounds on some statistical properties of the multitaper spectral estimate, which are similar to existing asymptotic results. We show using $K=2NW-O(\log (NW))$ tapers instead of the traditional $2NW-O(1)$ tapers better protects against spectral leakage, especially when the power spectrum has a high dynamic range. Our perspective also allows us to derive an $\epsilon $ -approximation to the multitaper spectral estimate which can be evaluated on a grid of frequencies using $O\left({\log (NW)\log \tfrac {1}{ \epsilon }}\right)$ FFTs instead of $K=O(NW)$ FFTs. This is useful in problems where many samples are taken, and thus, using many tapers is desirable. [ABSTRACT FROM AUTHOR]

High performance and, at the same time, energy efficiency are important yet often conflicting requirements in many fields of emerging applications. Those applications range from multi-dimensional and multi-sensor digital signal processing to machine learning, such as neural network processing. Whereas conventional fixed-point and floating-point processor architectures cannot adapt to quite diverging demands related to required precision and accuracy of computations, even within a single application, e.g., in different layers of a neural network, domain-specific accelerators may be much too specific and thus rigid to cover a wide enough spectrum of applications. In this tutorial brief, we give an overview of existing processor solutions that are reconfigurable or tunable in precision or accuracy of computations. The spectrum of reviewed architectures ranges from processors with vectorizable processors over multi- and trans-precision solutions, including GPUs to any-time instruction-set processors. The latter works with a fixed precision, but the accuracy of the result of floating-point operations is encoded in the instruction word. It can thus vary from instruction to instruction. This allows realizing accuracy vs. execution time or energy tradeoffs. Subsequently, we investigate several application domains, including neural network processing, linear algebra, and approximate computing, where such emerging processor architectures can be beneficially used. [ABSTRACT FROM AUTHOR]

The operation and maintenance of infrastructure components and systems can be modeled as a Markov process, partially or fully observable. Information about the current condition can be summarized by the “inner” state of a finite state controller. When a control policy is assigned, the stochastic evolution of the system is completely described by a Markov transition function. This article applies finite state Markov chain analyses to identify relevant features of the time evolution of a controlled system. We focus on assessing if some critical conditions are reachable (or if some actions will ever be taken), in identifying the probability of these critical events occurring within a time period, their expected time of occurrence, their long-term frequency, and the probability that some events occur before others. We present analytical methods based on linear algebra to address these questions, discuss their computational complexity and the structure of the solution. The analyses can be performed after a policy is selected for a Markov decision process (MDP) or a partially observable MDP. Their outcomes depend on the selected policy and examining these outcomes can provide the decision makers with deeper understanding of the consequences of following that policy, and may also suggest revising it. [ABSTRACT FROM AUTHOR]

Contribution: In this study, an alternative educational approach for introducing quantum computing to a wider audience is highlighted. The proposed methodology considers quantum computing as a generalized probability theory rather than a field emanating from physics and utilizes quantum programming as an educational tool to reinforce the learning process. Background: Quantum computing is a topic mainly rooted in physics, and it has been gaining rapid popularity in recent years. A need for extending the educational reach to groups outside of physics has also been becoming a necessity. Intended Outcomes: This study aims to inform academics and organizations interested in introducing quantum computing to a diverse group of participants on an educational approach. It is intended that the proposed methodology would facilitate people from diverse backgrounds to enter the field. Application Design: The introductory quantum physics content is bypassed and the quantum computing concepts are introduced through linear algebra instead. Quantum programming tasks are prepared in line with the content. Pre/post-test design method and Likert scale satisfaction surveys are utilized to measure knowledge acquisition and to evaluate the perception of the learning process by the participants. Findings: Conducted pre/post-test design survey shows that there is a statistically significant increase in the basic knowledge levels of the participants on quantum computing concepts. Furthermore, no significant difference in the gain scores is observed between the participants from different STEM-related educational backgrounds. The majority of the participants were satisfied and provided positive feedback. [ABSTRACT FROM AUTHOR]

Based on previous work and some related research [1]-[5], this author is able to develop a very interesting compact algorithm to compute the inverse of any nonsingular matrices, which could be real or complex. The mathematical formulation can be easily derived from the algorithm of the perturbed matrix inversion [1]. [ABSTRACT FROM AUTHOR]