Plamen Koev

Plamen Koev

Auto-generated profile, based on publicly available information

Plamen Koev

Department of Mathematics, San José State University, 1 Washington Square, San Jose, CA 95192, USA

Research Focus & Metrics

Academic Career Length

27Years (2000-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
19 January 2006 in Mathematics of Computation
Verified
Journal Article
Open access
PDF file
PKPlamen Koev
Plamen Koev
AEAlan Edelman
Alan Edelman
We present new algorithms that efficiently approximate the hypergeometric function of a matrix argument through its expansion as a series of Jack functions. Our algorithms exploit the combinatorial properties of the Jack function, and have complexity that is only linear in the size of the matrix.

1 January 2005 in SIAM Journal on Matrix Analysis and Applications
Verified
Journal Article
Closed access
JDJames Demmel
James Demmel
PKPlamen Koev
Plamen Koev
Vandermonde, Cauchy, and Cauchy--Vandermonde totally positive linear systems can be solved extremely accurately in O(n2 time using Björck--Pereyra-type methods. We prove that Björck--Pereyra-type methods exist not only for the above linear systems but also for any totally positive linear system as long as the initial minors (i.e., contiguous minors that include the first row or column) can be computed accurately. Using this result we design a new O(n2 Björck--Pereyra-type method for solving generalized Vandermonde systems of equations by using a new algorithm for computing the Schur function. We present explicit formulas for the entries of the bidiagonal decomposition, the LDU decomposition, and the inverse of a totally positive generalized Vandermonde matrix, as well as algorithms for computing these entries to high relative accuracy.

1 January 2005 in SIAM Journal on Matrix Analysis and Applications
Verified
Journal Article
Closed access
PKPlamen Koev
Plamen Koev
We consider the class of totally nonnegative (TN) matrices---matrices all of whose minors are nonnegative. Any nonsingular TN matrix factors as a product of nonnegative bidiagonal matrices. The entries of the bidiagonal factors parameterize the set of nonsingular TN matrices.We present new O(n3 ) algorithms that, given the bidiagonal factors of a nonsingular TN matrix, compute its eigenvalues and SVD to high relative accuracy in floating point arithmetic, independent of the conventional condition number. All eigenvalues are guaranteed to be computed to high relative accuracy despite arbitrary nonnormality in the TN matrix.We prove that the entries of the bidiagonal factors of a TN matrix determine its eigenvalues and SVD to high relative accuracy.We establish necessary and sufficient conditions for computing the entries of the bidiagonal factors of a TN matrix to high relative accuracy, given the matrix entries.In particular, our algorithms compute all eigenvalues and the SVD of TN Cauchy, Vandermonde, Ca...

1 January 2007 in SIAM Journal on Matrix Analysis and Applications
Verified
Journal Article
Closed access
PKPlamen Koev
Plamen Koev
We consider the problem of performing accurate computations with rectangular $(m\times n)$ totally nonnegative matrices. The matrices under consideration have the property of having a unique representation as products of nonnegative bidiagonal matrices. Given that representation, one can compute the inverse, LDU decomposition, eigenvalues, and SVD of a totally nonnegative matrix to high relative accuracy in $\mathcal{O}(\max(m^3,n^3))$ time—much more accurately than conventional algorithms that ignore that structure. The contribution of this paper is to show that the high relative accuracy is preserved by operations that preserve the total nonnegativity—taking a product, re-signed inverse (when $m=n$), converse, Schur complement, or submatrix of a totally nonnegative matrix, any of which costs at most $\mathcal{O}(\max(m^3,n^3))$. In other words, the class of totally nonnegative matrices for which we can do numerical linear algebra very accurately in $\mathcal{O}(\max(m^3,n^3))$ time (namely, those for wh...

1 April 2006 in Linear Algebra and its Applications
Verified
Journal Article
Closed access
PAP.-A. Absil
P.-A. Absil
AEA. Edelman
A. Edelman
PKP. Koev
P. Koev

25 April 2008 in Acta Numerica
Verified
Journal Article
Closed access
PDF file
JDJames Demmel
James Demmel
IDIoana Dumitriu
Ioana Dumitriu
OHOlga Holtz
Olga Holtz
PKPlamen Koev
Plamen Koev
We survey and unify recent results on the existence of accurate algorithms for evaluating multivariate polynomials, and more generally for accurate numerical linear algebra with structured matrices. By ‘accurate’ we mean that the computed answer has relative error less than 1,i.e., has some correct leading digits. We also address efficiency, by which we mean algorithms that run in polynomial time in the size of the input. Our results will depend strongly on the model of arithmetic: most of our results will use the so-calledtraditional model(TM), where the computed result of op(a,b), a binary operation likea+b, is given by op(a,b) * (1+δ) where all we know is that |δ| ≤ ε ≪ 1. Here ε is a constant also known as machine epsilon.We will see a common reason for the following disparate problems to permit accurate and efficient algorithms using only the four basic arithmetic operations: finding the eigenvalues of a suitably discretized scalar elliptic PDE, finding eigenvalues of arbitrary products, inverses, or Schur complements of totally non-negative matrices (such as Cauchy and Vandermonde), and evaluating the Motzkin polynomial. Furthermore, in all these cases the high accuracy is ‘deserved’,i.e., the answer is determined much more accurately by the data than the conventional condition number would suggest.In contrast, we will see that evaluating even the simple polynomialx+y+zaccurately is impossible in the TM, using only the basic arithmetic operations. We give a set of necessary and sufficient conditions to decide whether a high accuracy algorithm exists in the TM, and describe progress toward a decision procedure that will take any problem and provide either a high-accuracy algorithm or a proof that none exists.When no accurate algorithm exists in the TM, it is natural to extend the set of available accurate operations by a library of additional operations, such asx+y+z, dot products, or indeed any enumerable set which could then be used to build further accurate algorithms. We show how our accurate algorithms and decision procedure for finding them extend to this case.Finally, we address other models of arithmetic, and the relationship between (im)possibility in the TM and (in)efficient algorithms operating on numbers represented as bit strings.