PRISM :: Browsing by Author "Eberly, Wayne"

Browsing by Author "Eberly, Wayne"

Now showing 1 - 20 of 21

Open Access
ASYMPTOTICALLY EFFICIENT ALGORITHMS FOR THE FROBENIUS FORM
(2000-05-03) Eberly, Wayne
A new randomized algorithm is presented for computation of the Frobenius form of an n x n matrix over a field. A version of the algorithm is presented that uses standard arithmetic whose asymptotic expected complexity matches the worst case complexity of the best known deterministic algorithm for this problem, recently given by Storjohann and Villard [25], and that seems to be superior when applied to sparse or structured matrices with a small number of invariant factors. A version that uses asymptotically fast matrix multiplication is also presented. This is the first known algorithm for this computation over small fields whose asymptotic complexity matches that of the best algorithm for computations over large fields and that also provides a Frobenius transition matrix over the ground field. As an application, it is shown that a "rational Jordan form" of an n x n matrix over a finite field can also be computed asymptotically efficiently.
Open Access
Black Box Linear Algebra: Extending Wiedemann’s Analysis of a Sparse Matrix Preconditioner for Computations over Small Fields
(ACM Communications in Computer Algebra, 2018-05-03) Eberly, Wayne
Wiedemann’s paper, introducing his algorithm for sparse and structured matrix computations over arbitrary fields, also presented a pair of matrix preconditioners for computations over small fields. The analysis of the second of these is extended in order to provide more explicit statements of the expected number of nonzero entries in the matrices obtained as well as bounds on the probability that such matrices have maximal rank. This is part of ongoing work to establish that this matrix preconditioner can also be used to bound the number of nontrivial nilpotent blocks in the Jordan normal form of a preconditioned matrix, in such a way that one can also sample uniformly from the null space of the originally given matrix. If successful this will result in a black box algorithm for the type of matrix computation required when using the number field sieve for integer factorization that is provably reliable and — by a small factor — asymptotically more efficient than alternative techniques that make use of other matrix preconditioners or require computations over field extensions.
Open Access
Bounding the Nullities of Random Block Hankel Matrices: An Alternative Approach
(2005-05-10) Eberly, Wayne; Hovinen, Bradford
Bounds are developed for the probability that various randomly generated block Hankel matrices are rank-deficient. These bounds are potentially of use to analyze the efficiency and reliability of various randomized block Wiedemann and block Lanczos algorithms, that are either currently under development or now in use, when these are applied to solve systems of linear equations and sample from the null space of matrices over small finite fields. The bounds that are presented here resemble ones that have previously been obtained using other arguments or that could likely be obtained by straightforward extensions of arguments that have recently been presented. The method used to obtain these bounds in this report is rather different and may be of some interest in its own right: It relies only on estimates of the number of irreducible polynomials of a given degree over a finite field and on elementary linear algebra.
Open Access
Early Termination over Small Fields II: On the Reliability of Block Krylov-Based Algorithms in a Generic Case
(2014-07-15) Eberly, Wayne
Block Hankel matrices, generated according to a particular distribution, arise in the analysis of Block Wiedemann and Block Lanczos algorithms. It is shown that if the input matrix A has entries in a small finite field Fq and satisfies a condition that holds generically, then the expected nullities of these matrices are low — as needed to establish the efficiency and reliability of these algorithms. A sparse matrix preconditioner, that ensures that the above-mentioned condition holds with high probability, is also contributed.
Open Access
Early Terminiation over Small Fields
(2003-06-12) Eberly, Wayne
Krylov-based algorithms have recently been used (alone, or in combination with other methods) in order to solve systems of linear equations that arise during integer factorization and discrete logarithm computations. Since these include systems over small finite fields, the behavior of these algorithms in this setting is of interest. Unfortunately, the application of these methods is complicated by the possibility of several kinds of breakdown. Orthogonal vectors can arise when a variant of the Lanczos algorithm is used to generate a basis, and zero-discrepancies can arise during the computation of minimal polynomials of linearly recurrent sequences when Wiedemann's algorithm is applied. Several years ago, Austin Lobo reported experimental evidence that zero-discrepancies are extremely unlikely when a randomized version of Wiedemann's algorithm is applied to solve systems over large fields. With high probability, results are correct if a computation is terminated as soon as such a sequence is detected. "Early termination" has consequently been included in recent implementations. In this paper, we analyze the probability of long sequences of zero-discrepancies during computations of minimal polynomials of the linearly recurrent sequences that arise when simple Krylov-based algorithms are used to solve systems over very small finite fields. Variations of these algorithms that incorporate early termination are briefly presented and analyzed in the small field case.
Open Access
EFFICIENT ALGORITHMS FOR THE DECOMPOSITION OF MATRIX ALGEBRAS
(1990-08-01) Eberly, Wayne
We consider the bit-complexity of the decomposition of semi-simple algebras over finite fields and number fields, and of simple algebras over C and R, for matrix algebras with bases consisting of matrices over a number field. Exact computations in number fields are performed symbolically. We present new probabilistic and deterministic polynomial-time algorithms for the decomposition of semi-simple algebras over the above concrete fields. The algorithms are somewhat simpler than the algorithm previously given by Friedl and Ronyai; the probabilistic algorithm suggests a modification that might improve the performance of the original algorithm in the average case. The new methods also provide parallel (NC) reductions from the decomposition of semi-simple algebras to the problem of factoring polynomials over fields, as well as efficient parallel algorithms for the decomposition of semi-simple algebras over (small) finite fields. We also extend the methods of Eberly [8] and Babai and Ronyai [1] for the decomposition of simple algebras over C, to obtain a new probabilistic polynomial-time algorithm for the decomposition of simple algebras over R. This is the first (Boolean) polynomial-time algorithm for this problem.
Open Access
Efficient exact parallel matrix inversion
(1995) Zhang, Wei; Eberly, Wayne
Open Access
Efficient Multiparty Computation from Lossy Threshold Encryption
(2019-09-26) Nargis, Isheeta; Eberly, Wayne; Jacobson, Michael S.; Safavi-Naini, Reihaneh S.; Fong, Philip W. L.; Reardon, Joel; Yadid-Pecht, Orly; Wei, Ruizhong
This dissertation includes four contributions concerning secure multiparty computation. The first contribution is a new lossy threshold encryption scheme. This is the first encryption scheme that is both a lossy and a threshold encryption scheme. The second contribution is a new oblivious transfer protocol secure against erasure-free one-sided active adaptive adversaries. The third contribution is a new two-party computation protocol for the evaluation of boolean circuits that is secure against erasure-free one-sided active adaptive adversaries. As a building block of this protocol, a new cut-and-choose oblivious transfer protocol is designed. The fourth contribution is a new multiparty computation protocol for the evaluation of arithmetic circuits that is secure against covert adversaries. Protocols that are part of the second, third and fourth contributions improve the communication complexity, the number of public key encryption operations and the number of exponentiation operations over existing protocols for the same problems that provide the same or higher levels of security.
Open Access
FAST PARALLEL BAND MATRIX ARITHMETIC
(1990-08-01) Eberly, Wayne
We present parallel algorithms for computation of the determinant, adjoint, characteristic polynomial and rank of band matrices, and for the solution of systems of linear equations with band matrices as coefficient matrices. The algorithms can be implemented using arithmetic-boolean circuits of polynomial size and depth O(log n logm), or depth O(log n log m + log n log log n) for computations over small finite fields, where n is the order and m the band width of the matrix given as input. They can be implemented for computations over number fields and finite fields using log space uniform boolean circuits of depth O(log n log m + log n log log n) and polynomial size, for input size n and band width m.
Open Access
LOGARITHMIC DEPTH CIRCUITS FOR HERMITE INTERPOLATION
(1990-07-01) Eberly, Wayne
We present a new parallel algorithm for Hermite interpolation. The algorithm can be implemented using arithmetic-boolean circuits of depth logarithmic and size polynomial in the input size. A corresponding Boolean algorithm can be used to compute the coefficients of the Hermite interpolating polynomial from binary representations of evaluation points and derivatives over finite fields and number fields, using a P-uniform family of circuits of depth logarithmic in the input size and of polynomial size.
Open Access
A New Interactive Certificate for Matrix Rank
(2015-07-07) Eberly, Wayne
A new interactive certificate for matrix rank, based on the certification of a maximal nonsingular submatrix, is described. Versions of this for matrices over abstract fields and integer matrices are each described.
Open Access
On the complexity of computing characters of finite groups
(1994) Hepler, Charles Thomas; Eberly, Wayne
Open Access
Optimization of Quantum Algorithms for Applications
(2022-05-04) Nerem, Robert Riley; Sanders, Barry; Hoyer, Peter; Gour, Gilad; Eberly, Wayne; Braverman, Elena
I aim to design and evaluate quantum algorithms that perform optimally with respect to metrics that make or break the applicability of these algorithms. Specifically, I analyze two applications: Bitcoin mining and estimating expectation values from a system of linear equations. For the former I develop a quantum algorithm for Bitcoin mining which optimizes the probability of successfully mining Bitcoin. For the later I give a quantum algorithm with query complexity that is optimally dependent on accuracy. I ensure that my quantum algorithms are relevant to applications by designing algorithms that are end-to-end for their applications, as opposed to algorithms that only address a subroutine. My work yields quantum algorithms that are directly comparable to their classical counterparts. By making this comparison, I develop necessary conditions for quantum algorithms to outperform classical algorithms at solving systems of linear equations and Bitcoin mining.
Open Access
Randomized algorithms for solving nonsingular linear systems and computing matrix rank
(2002) Chen, Xuming; Eberly, Wayne
Open Access
Reliable Krylov-based Algorithms for Matrix Null Space
(2004-12-20) Eberly, Wayne
Krylov-based algorithms have recently been used, in combination with other methods, to solve systems of linear equations and to perform related matrix computations over finite fields. For example, large and sparse systems of linear equations over F 2 are formed during the use of the number field sieve for integer factorization, and elements of the null space of these systems are sampled. Block Lanczos algorithms have been used to perform this computation with considerable success. However, the algorithms that are currently in use do not appear to be reliable in the worst case. This report presents a block Lanczos algorithm that is somewhat simpler than block algorithms that are presently in use and provably reliable for computations over large fields. This can be implemented, using a field extension, in order to produce several uniformly and independently selected elements from the null space at once. The amortized cost to produce each vector closely matches the cost to generate such a vector with the methods currently in use. An algorithm is also given to compute the rank of a matrix A E F m x n over a small finite field F. The expected number of matrix-vector products by A or A t used by this algorithm is in O (r), where r is the rank of A. The expected number of additional field operations used by this algorithm is within a polylog factor of r (n+m), and the expected storage space is within a polylog factor of n + m. This is asymptotically more efficient than existing black box algorithms to compute the rank of a matrix over a small field, assuming that the cost of matrix-vector products dominates the cost of other operations.
Open Access
Selecting Algorithms for Black Box Matrices: Checking for Matrix Properties That Can Simplify Computations
(2016-11-02) Eberly, Wayne
Processes to automate the selection of appropriate algorithms for various matrix computations are described. In particular, processes to check for, and certify, various matrix properties of black-box matrices are presented. These include sparsity patterns and structural properties that allow “superfast” algorithms to be used in place of black box algorithms. Matrix properties that hold generically, and allow the use of matrix preconditioning to be reduced or eliminated, can also be checked for and certified — notably including in the small-field case, where this presently has the greatest impact on the efficiency of the computation.
Open Access
Simulation Modeling of Calgary's E-Scooter System
(2021-09) Mclean, Rachel; Williamson, Carey; Kattan, Lina; Samavati, Faramarz; Demissie, Merkebe; Eberly, Wayne; Williamson, Carey; Kattan, Lina
Shared micromobility is a rapidly growing transportation technology, with several companies establishing e-bike and e-scooter programs in cities across the globe. This thesis analyzes two years of empirical data on e-scooter usage from a shared mobility pilot program in the City of Calgary to create a synthetic workload model of e-scooter traffic. A synthetic workload generator is developed from this model and incorporated into a dedicated, custom-built simulation environment. This simulation is used to conduct experiments evaluating the impacts of different e-scooter management policies and infrastructure, such as fleet size, battery re-charging strategies, and urban parking infrastructure locations, on the efficacy of the shared e-scooter system. The results of these simulation experiments detail the impacts of these policies on satisfied user demand, costs of collecting depleted scooters to be recharged, and number of improperly parked scooters, and highlight the importance of proper site selection for parking areas and battery charging infrastructure.
Open Access
SIZE-DEPTH TRADEOFFS FOR ALGEBRAIC FORMULAE
(1992-05-01) Eberly, Wayne; Cleve, Richard; Bshouty, Nader H.
We prove some tradeoffs between the size and depth of algebraic formulae. In particular, we show that, for any fixed $ epsilon~>~O$, any algebraic formula of size \s+1Ss-1 can be converted into an equivalent formula of depth $\s+1O\s-1 (log \s+1S\s-1)$ and size $O(S sup {1+ epsilon})$. This result is an improvement over previously-known results where, to obtain the same depth bound, the formula-size is $ OMEGA (S sup alpha )$, with $ alpha~>=~2$.
Open Access
Sparse Matrix Computations over Small Fields: A Simpler Block Lanczos Algorithm and Its Analysis
(2013-05-29) Eberly, Wayne
A simpli ed \block Lanczos" algorithm is presented and its correctness established. While its e ciency in the general case is not proved, preconditioning used for similar algo- rithms is also su cient here. Results concerning reliability and e ciency may be of more general interest because they may serve to (somewhat) better explain the performance of other block algorithms, including block Wiedemann algo- rithms and algorithms that use rectangular blocking.
Open Access
Strongly Linearizable LL/SC from CAS
(2024-12-06) Naderi Semiromi, Fatemeh; Woelfel, Philipp; Eberly, Wayne; Censor-Hillel, Keren
Linearizability is the standard correctness condition for shared memory algorithms and is generally considered to be the practical equivalent of atomicity for deterministic algorithms. However, Golab, Higham, and Woelfel [16] showed that if we replace atomic objects used in a randomized algorithm with their linearizable implementations, then some of the properties of the algorithm may be lost. They introduced a stronger correctness condition, called strong linearizability, and proved that strongly linearizable objects can be used in both deterministic and randomizes algorithms as if they were atomic. In this thesis, we present an efficient strongly linearizable implementation of the load-linked/ store-conditional (LL/SC) primitive from compare-and-swap (CAS) objects. Our algorithm has constant step complexity, and uses a bounded number of CAS objects and registers that can each store O(log n) bits, where n is the number of processes. To the best of our knowledge, we are the first ones introducing a constant-time strongly linearizable LL/SC implementation, which uses bounded memory and bounded word-size.