Search

This paper proposes the matrix representation of formal polynomials over max-plus algebra and obtains the maximum and minimum canonical forms of a polynomial function by standardizing this representation into a canonical form. A necessary and sufficient condition for two formal polynomials corresponding to the same polynomial function is derived. Such a matrix method is constructive and intuitive, and leads to a polynomial algorithm for factorization of polynomial functions. Some illustrative examples are presented to demonstrate the results. [ABSTRACT FROM AUTHOR]

Medical imaging tasks, such as segmentation, 3D modeling, and registration of medical images, involve complex geometric problems, usually solved by standard linear algebra and matrix calculations. In the last few decades, conformal geometric algebra (CGA) has emerged as a new approach to geometric computing that offers a simple and efficient representation of geometric objects and transformations. However, the practical use of CGA-based methods for big data image processing in medical imaging requires fast and efficient implementations of CGA operations to meet both real-time processing constraints and accuracy requirements. The purpose of this study is to present a novel implementation of CGA-based medical imaging techniques that makes them effective and practically usable. The paper exploits a new simplified formulation of CGA operators that allows significantly reduced execution times while maintaining the needed result precision. We have exploited this novel CGA formulation to re-design a suite of medical imaging automatic methods, including image segmentation, 3D reconstruction and registration. Experimental tests show that the re-formulated CGA-based methods lead to both higher precision results and reduced computation times, which makes them suitable for big data image processing applications. The segmentation algorithm provides the Dice index, sensitivity and specificity values of 98.14%, 98.05% and 97.73%, respectively, while the order of magnitude of the errors measured for the registration methods is 10-5. [ABSTRACT FROM AUTHOR]

In a paper published in 2013, Wang and Ma proposed a structure-preserving algorithm for computing the quaternion LU decomposition. They claimed that it was faster than the LU decomposition implemented in the quaternion Toolbox for Matlab (QTFM). But in 2015, Sangwine, one of the authors of QTFM, pointed out that the tests carried out by him did not support Wang and Ma's claim. We studied the structure-preserving algorithm of Wang and Ma, and found that the computations were based on element to element operations. In this paper, we re-propose real structure-preserving methods for the quaternion LU decomposition and partial pivoting quaternion LU decomposition, which make full use of high-level operations, and relation of operations between quaternion matrices and their real representation matrices. These algorithms are more efficient than that in QTFM using quaternion arithmetics. Numerical experiments are provided to demonstrate the efficiency of the real structure-preserving method. [ABSTRACT FROM AUTHOR]

The paper establishes the invariance of the simplex-module algorithm for expanding real numbers α = (α1, …, αd) in multidimensional continued fractions under linear-fractional transformations α′=α1′…αd1=Uα with matrices U from the unimodular group GLd+1(ℤ). It is shown that the convergents of the transformed collections of numbers α′ satisfy the same recurrence relation and have the same approximation order. [ABSTRACT FROM AUTHOR]

We present a method for computing a basis of localized orthonormal orbitals (both occupied and virtual), in whose representation the Fock matrix is extremely diagonal dominant. The existence of these orbitals is shown empirically to be sufficient for achieving highly accurate second-order Møller-Plesset (MP2) energies, calculated according to Kapuy’s method. This method (which we abbreviate KMP2) involves a different partitioning of the n-electron Hamiltonian and scales at most quadratically, with potential for linearity, in the number of electrons. As such, we believe the KMP2 algorithm presented here could be the basis of a viable approach to local-correlation calculations.© 2005 American Institute of Physics. [ABSTRACT FROM AUTHOR]

Software test suites based on the concept of interaction testing are very useful for testing software components in an economical way. Test suites of this kind may be created using mathematical objects called covering arrays. A covering array, denoted by CA(N; t, k, v), is an N × k array over with the property that every N × t sub-array covers all t-tuples of at least once. Covering arrays can be used to test systems in which failures occur as a result of interactions among components or subsystems. They are often used in areas such as hardware Trojan detection, software testing, and network design. Because system testing is expensive, it is critical to reduce the amount of testing required. This paper addresses the Optimal Shortening of Covering ARrays (OSCAR) problem, an optimization problem whose objective is to construct, from an existing covering array matrix of uniform level, an array with dimensions of (N − δ) × (k − Δ) such that the number of missing t-tuples is minimized. Two applications of the OSCAR problem are (a) to produce smaller covering arrays from larger ones and (b) to obtain quasi-covering arrays (covering arrays in which the number of missing t-tuples is small) to be used as input to a meta-heuristic algorithm that produces covering arrays. In addition, it is proven that the OSCAR problem is NP-complete, and twelve different algorithms are proposed to solve it. An experiment was performed on 62 problem instances, and the results demonstrate the effectiveness of solving the OSCAR problem to facilitate the construction of new covering arrays. [ABSTRACT FROM AUTHOR]

In this paper, we derive novel representations of generalized inverses $$A^{(1)}_{T,S}$$ and $$A^{(1,2)}_{T,S}$$ , which are much simpler than those introduced in Ben-Israel and Greville (Generalized inverses: theory and applications. Springer, New York, 2003). When $$A^{(1,2)}_{T,S}$$ is applied to matrices of index one, a simple representation for the group inverse $$A_{g}$$ is derived. Based on these representations, we derive various algorithms for computing $$A^{(1)}_{T,S}$$ , $$A^{(1,2)}_{T,S}$$ and $$A_{g}$$ , respectively. Moreover, our methods can be achieved through Gauss-Jordan elimination and complexity analysis indicates that our method for computing the group inverse $$A_{g}$$ is more efficient than the other existing methods in the literature for a large class of problems in the computational complexity sense. Finally, numerical experiments show that our method for the group inverse $$A_{g}$$ has highest accuracy among all the existing methods in the literature and also has the lowest cost of CPU time when applied to symmetric matrices or matrices with high rank or small size matrices with low rank in practice. [ABSTRACT FROM AUTHOR]

This paper starts a series of publications devoted to surveying and developing methods for solving algebraic problems for two-parameter polynomial and rational matrices. The paper considers rank factorizations and, in particular, the relatively irreducible and ΔW-2 factorizations, which are used in solving spectral problems for two-parameter polynomial matrices F(λ, µ). Algorithms for computing these factorizations are suggested and applied to computing points of the regular, singular, and regular-singular spectra and the corresponding spectral vectors of F(λ, µ). The computation of spectrum points reduces to solving algebraic equations in one variable. A new method for computing spectral vectors for given spectrum points is suggested. Algorithms for computing critical points and for constructing a relatively free basis of the right null-space of F(λ, µ) are presented. Conditions sufficient for the existence of a free basis are established, and algorithms for checking them are provided. An algorithm for computing the zero-dimensional solutions of a system of nonlinear algebraic equations in two variables is presented. The spectral properties of the ΔW-2 method are studied. Bibliography: 4 titles. [ABSTRACT FROM AUTHOR]

We present a stable and practical algorithm that uses QR factors of the Sylvester matrix to compute the greatest common divisor (GCD) of univariate approximate polynomials over R[x] or C[x]. An approximate polynomial is a polynomial with coefficients that are not known with certainty. The algorithm of this paper improves over previously published algorithms by handling the case when common roots are near to or outside the unit circle, by splitting and reversal if necessary. The algorithm has been tested on thousands of examples, including pairs of polynomials of up to degree 1000, and is now distributed as the program QRGCD in the SNAP package of Maple 9. [ABSTRACT FROM AUTHOR]

This paper presents a new implementation of the VAST algorithm for principal and minor subspace tracking. VAST was initially derived from the Subspace Projection (SP) algorithm by Davila, which was known for its exceptional convergence rate, compared with other classical principal subspace trackers. The novelty in the VAST algorithm was the lower computational cost (linear if the data correlation matrix satisfies a so-called shift-invariance property), and the extension to minor subspace tracking. However, the original implementation of the YAST algorithm suffered from a numerical stability problem (the subspace weighting matrix slowly loses its orthonormality). We thus propose in this paper a new implementation of VAST, whose stability is established theoretically and tested via numerical simulations. This algorithm combines all the desired properties for a subspace tracker: remarkably high convergence rate, lowest steady-state error, linear complexity, and numerical stability regarding the orthonormality of the subspace weighting matrix. [ABSTRACT FROM AUTHOR]

In many scientific applications, dynamic data redistribution is used to enhance algorithm performance and achieve data locality in parallel programs on distributed memory multi-computers. In this paper, we present a new method, Compressed Diagonals Remapping (CDR) technique aims to the efficiency of runtime data redistribution on banded sparse matrices. The main idea of the proposed technique is first to compress the source matrix into a Compressed Diagonal Matrix (CDM) form. Based on the compressed diagonal matrix, a one-dimensional local and global index transformation method can be applied to carry out data redistribution on the compressed diagonal matrix. This process is identical to redistribute data in the two-dimensional banded sparse matrix. The CDR technique uses an efficient one-dimensional indexing scheme to perform data redistribution on banded sparse matrix. A significant improvement of this approach is that a processor does not need to determine the complicated sending or receiving data sets for dynamic data redistribution. The indexing cost is reduced significantly. The second advantage of the present techniques is the achievement of optimal packing/unpacking stages consequent upon the consecutive attribute of column elements in a compressed diagonal matrix. Another contribution of our methods is the ability to handle sparse matrix redistribution under two disjoint processor grids in the source and destination phases. A theoretical model to analyze the performance of the proposed technique is also presented in this paper. To evaluate the performance of our methods, we have implemented the present techniques on an IBM SP2 parallel machine along with the v2m algorithm and a dense redistribution strategy. The experimental results show that our technique provides significant improvement for runtime data redistribution of banded sparse matrices in most test samples. [ABSTRACT FROM AUTHOR]

In (SIAM J. Matrix Anal. Appl., 23 (2002), pp. 706–727, we developed numerical algorithms for computing sparse low-rank approximations of matrices, and we also provided a detailed error analysis of the proposed algorithms together with some numerical experiments. The low-rank approximations are constructed in a certain factored form with the degree of sparsity of the factors controlled by some user-specified parameters. In this paper, we cast the sparse low-rank approximation problem in the framework of penalized optimization problems. We discuss various approximation schemes for the penalized optimization problem which are more amenable to numerical computations. We also include some analysis to show the relations between the original optimization problem and the reduced one. We then develop a globally convergent discrete Newton-like iterative method for solving the approximate penalized optimization problems. We also compare the reconstruction errors of the sparse low-rank approximations computed by our new methods with those obtained using the methods in the earlier paper and several other existing methods for computing sparse low-rank approximations. Numerical examples show that the penalized methods are more robust and produce approximations with factors which have fewer columns and are sparser. [ABSTRACT FROM AUTHOR]

In this paper we study the inversion of an analytic matrix valued function A(z). This problem can also be viewed as an analytic perturbation of the matrix A0 = A(0). We are mainly interested in the case where A0 is singular but A(z) has an inverse in some punctured disc around z = 0. It is known that A-1 (z) can be expanded as a Laurent series at the origin. The main purpose of this paper is to provide efficient computational procedures for the coefficients of this series. We demonstrate that the proposed algorithms are computationally superior to symbolic algebra when the order of the pole is small. [ABSTRACT FROM AUTHOR]

This paper considers the problem of approximating a given symmetric matrix by a symmetric matrix with a prescribed spectrum so that the Frobenius norm of the matrix difference is minimized. By the introduction of a variable search direction, a new convergent algorithm for solving the problem is derived, which is guaranteed to be convergent and is capable of achieving a fast rate of convergence. It is shown that the set of fixed points of the proposed algorithm coincides with the set of equilibrium points of the original double bracket equation. A numerical example is presented to demonstrate superior performance of the proposed algorithm over a standard double bracket algorithm. [ABSTRACT FROM AUTHOR]

In the last years, Geometric Algebra with its Euclidean, Homogeneous and Conformal models attracts the research interest in many areas of Computer Science and Engineering and particularly in Computer Graphics as it is shown that they can produce more efficient and smooth results than other algebras. In this paper, we present an all-inclusive algorithm for real-time animation interpolation and GPU-based geometric skinning of animated, deformable virtual characters using the Conformal model of Geometric Algebra (CGA). We compare our method with standard quaternions, linear algebra matrices and dual-quaternions blending and skinning algorithms and we illustrate how our CGA-GPU inclusive skinning algorithm can provide as smooth and more efficient results as state-of-the-art previous methods. Furthermore, the elements of CGA that handle transformations (CGA motors) can support translation, rotation and dilation(uniform scaling) of joints under a single, GPU-supported mathematical framework and avoid conversion between different mathematical representations in contrast to quaternions and dual-quaternions that support only rotation and rotation-translation, respectively. Hence, our main novelty is the replacement of different types of algebras, and their in-between conversions between CPU and GPU, such as linear algebra matrices, quaternions, dual-quaternions and Euler angles for animation interpolation and skinning with a single mathematical representation, the CGA motors which can optimally handle the composition of translation, rotation and scaling joint transformations and interpolations. Employing latest CGA code generators, we provide a sample implementation of our algorithm running natively in a vertex shader program on modern GPUs for typical deformable virtual character simulations. [ABSTRACT FROM AUTHOR]

The paper discusses the method of hereditary pencils for computing points of the regular and singular spectra of a general two-parameter polynomial matrix. The method allows one to reduce the spectral problems considered to eigenproblems for polynomial matrices and pencils of constant matrices. Algorithms realizing the method are suggested and justified. Bibliography: 4 titles. [ABSTRACT FROM AUTHOR]

In this paper we pursue the propositional calculus and the SATisfiability solvers as a powerful declarative programming environment that makes it possible to create and run the propositional declarative programs for computational tasks in various areas of mathematics. We report some experimental results on our application of the propositional SATisfiability environment to computing some simple orthogonal matrices and the orders of some orthogonal groups. Some encouraging (and not very encouraging) experiments are reported for the proposed propositional search procedures using off-the-shelf general-purpose SAT solvers. Our new software toolkit SAT4Alg is announced. [ABSTRACT FROM AUTHOR]

The communication cost of algorithms (also known as I/O-complexity) is shown to be closely related to the expansion properties of the corresponding computation graphs.We demonstrate this on Strassen's and other fast matrix multiplication algorithms, and obtain the first lower bounds on their communication costs. In the sequential case, where the processor has a fast memory of size M, too small to store three n-by-n matrices, the lower bound on the number of words moved between fast and slow memory is, for a large class of matrix multiplication algorithms, Ω((n/√M)ω0 ·M), where ω0 is the exponent in the arithmetic count (e.g., ω0 = lg 7 for Strassen, and ω0 = 3 for conventional matrix multiplication). With p parallel processors, each with fast memory of size M, the lower bound is asymptotically lower by a factor of p. These bounds are attainable both for sequential and for parallel algorithms and hence optimal. [ABSTRACT FROM AUTHOR]

We consider the conic feasibility problem associated with the linear homogeneous system Ax≤0, x≠0. The complexity of iterative algorithms for solving this problem depends on a condition number C( A). When studying the typical behavior of algorithms under stochastic input, one is therefore naturally led to investigate the fatness of the tails of the distribution of C( A). Introducing the very general class of uniformly absolutely continuous probability models for the random matrix A, we show that the distribution tails of C( A) decrease at algebraic rates, both for the Goffin–Cheung–Cucker number C G and the Renegar number C R. The exponent that drives the decay arises naturally in the theory of uniform absolute continuity, which we also develop in this paper. In the case of C G, we also discuss lower bounds on the tail probabilities and show that there exist absolutely continuous input models for which the tail decay is subalgebraic. [ABSTRACT FROM AUTHOR]

Periodic nonuniform sampling can be used to achieve sub-Nyquist sampling of bandlimited multiband signals. In this paper, we examine the question of selecting the sampling pattern in such a scheme, so that the reconstruction robustness—measured by the condition-number of the modulation matrix—is maximized. Contrary to previous work, where the sampling pattern was chosen from a discrete set, we let the sampling patterns vary continuously, but impose a structural constraint. Using this approach, we derive necessary and sufficient conditions on the spectral support of the signal for which perfect conditioning exist, namely, for which a sampling pattern can be found so that the resulting modulation matrix has a condition number equal to 1. A simple test to check for these conditions is developed and the desired sampling patterns are found. An algorithm for choosing the sampling pattern when the aforementioned conditions are not satisfied is also introduced. Finally, we present some simulation results. [ABSTRACT FROM AUTHOR]

Recently a new least-squares primal-dual (LSPD) algorithm, that is impervious to degeneracy, has effectively been applied to solving linear programming problems by Barnes et al, 2002. In this paper, we show an application of LSPD to shortest path problems with nonnegative arc length is equivalent to the Dijkstra's algorithm. We also compare the LSPD algorithm with the conventional primal-dual algorithm in solving shortest path problems and show their difference due to degeneracy in solving the 1-1 shortest path problems. [ABSTRACT FROM AUTHOR]

An ant colony optimization (ACO) application to a fuzzy controller (FC) design, called ACO-FC, is proposed in this paper for improving design efficiency and control performance, as well as ACO hardware implementation. An FC's antecedent part, i.e., the "if" part of its composing fuzzy if-then rules, is partitioned in grid-type, and all candidate rule consequent values are then listed. An ant trip is regarded as a combination of consequent values selected from every rule. A pheromone matrix among all candidate consequent values is constructed. Searching for the best one among all combinations of rule consequent values is based mainly on the pheromone matrix. The proposed ACO-FC performance is shown to be better than other metaheuristic design methods on simulation examples. The ACO used in ACO-FC is based on the known ant colony system and is hardware implemented on a field-programmable gate array chip. The ACO chip application to fuzzy control of a simulated water bath temperature control problem has verified the designed chip effectiveness. [ABSTRACT FROM AUTHOR]

When a dissimilarity matrix cannot be represented in a Euclidean space, it is possible to make it Euclidean by means of suitable transformations of the original dissimilarity values. In this paper we discuss some interesting properties of a class of transformations based on adding a specific squared Euclidean distance to the initial dissimilarity. [ABSTRACT FROM AUTHOR]

In this paper, a new optimal root locus technique is presented. It relies on the choice of the performance index in the linear quadratic regulator (LQR) problem. The choice of the states weighting matrix Q is made so that the solution of the resulting algebraic Riccati equation (ARE) is known in advance. This eliminates the need to solve the (2n x 2n) eigenvalue/eigenvector problem usually needed to solve the ARE. With this choice of Q, the solution of the ARE becomes a constant multiple of the observability Gramian. The control law is easily calculated in O(n²) flops. This is a good improvement over the Chang-Letov method, which in general requires O(2n)3 flops. The weighting matrix Q, the Feedback control gain K, and the cost J are directly given ms functions of the observability Gramian. Although the algorithm is given for any coordinate system, the development in balanced coordinates is particularly interesting. In this coordinate system, Q, K, and J are directly given as functions of the observability and controllability Gramians and the Hankel singular values of the system. Finally, it is shown that the optimal root locus can be obtained using ordinary root locus and develops efficient rules and algorithms. [ABSTRACT FROM AUTHOR]

In this paper we describe a method for continuing periodic solution bifurcations in periodic delay-differential equations. First, the notion of characteristic matrices of periodic orbits is introduced and equivalence with the monodromy operator is demonstrated. An alternative formulation of the characteristic matrix is given, which can be computed efficiently. Defining systems of bifurcations are constructed in a standard way, including the characteristic matrix and its derivatives. For following bifurcation curves in two parameters, the pseudo-arclength method is used combined with Newton iteration. Two test examples (an interrupted machining model and a traffic model with driver reaction time) conclude the paper. The algorithm has been implemented in the software tool PDDE-CONT. [ABSTRACT FROM AUTHOR]

Optimality in the range space is expressed as a tangency condition for an affine set and a cone. In a previous paper, an algorithm was introduced that reaches tangency keeping the two sets nonintersecting. Here,we introduce an exact finite-convergence evolutive algorithm that reaches tangency while keeping the two sets intersecting. In the process of developing the algorithm, we add some completion to the theory (e.g., the description of the contact polytope). Furthermore, we introduce a new formula to express the maximum, which is the primal counterpart of the dual formula introduced in a previous paper. [ABSTRACT FROM AUTHOR]

The problem of computing the system's Failure Frequency is reduced to the problem of computing its Availability. This is performed by a transformation operator. However, the existing transformation operator is not practical because its transformation time increases exponentially with system size. To overcome this difficulty, this paper proposes a new method of transforming the Availability expression of a system into the corresponding Failure Frequency expression of the system. This method is based on a matrix approach using a 2 × 2 matrix consisting of 0, Availability, and Failure Frequency in an appropriate manner. This transformation also enables algorithms for Computing the Availability of a system to be transformed into algorithms for computing its Failure Frequency by replacing parameters and operations with matrix parameters and operations. The computation time after transformation is linear with respect to the original Availability algorithm. This implies that the problems of computing other well-known reliability measures including, Availability, Unavailability, MTBF, MTTR, MCT, Failure Rate, Failure Rate, and Failure Frequency, are reduced to only the Availability computation problem. [ABSTRACT FROM AUTHOR]

In this paper we propose a new class of primal-dual path-following interior point algorithms for solving monotone linear complementarity problems. At each iteration, the method would select a target on the central path with a large update from the current iterate, and then the Newton method is used to get the search directions, followed by adaptively choosing the step sizes, which are, e.g., the largest possible steps before leaving a neighborhood that is as wide as the given ${\cal N}^-_{\infty}$ neighborhood. The only deviation from the classical approach is that we treat the classical Newton direction as the sum of two other directions, corresponding to, respectively, the negative part and the positive part of the right-hand side. We show that if these two directions are equipped with different and appropriate step sizes, then the method enjoys the low iteration bound of $O(\sqrt{n}\log L)$, where $n$ is the dimension of the problem and $L=\frac{(x^0)^Ts^0}{\ep}$ with $\ep$ the required precision and $(x^0,s^0)$ the initial interior solution. For a predictor-corrector variant of the method, we further prove that, besides the predictor steps, each corrector step also reduces the duality gap by a rate of $1-1/O(\sqrt{n})$. Additionally, if the problem has a strict complementary solution, then the predictor steps converge Q-quadratically. [ABSTRACT FROM AUTHOR]

The active appearance model (AAM) is a powerful tool for modeling images of deformable objects and has been successfully used in a variety of alignment, tracking, and recognition applications. AAM uses subspace-based deformable models to represent the images of a certain object class. In general, fitting such complicated models to previously unseen images using standard optimization techniques is a computationally complex task because the gradient matrix has to be numerically computed at every iteration. The critical feature of AAM is a fast convergence scheme which assumes that the gradient matrix is fixed Around the optimal coefficients for all images. Our work in this paper starts with the observation that such a fixed gradient matrix inevitably specializes to a certain region in the texture space, and the fixed gradient matrix is not a good estimate of the actual gradient as the target texture moves away from this region. Hence, we propose an adaptive AAM algorithm that linearly adapts the gradient matrix according to the composition of the target image's texture to obtain a better estimate for the actual gradient. We show that the adaptive AAM significantly outperforms the basic AAM, especially in images that are particularly challenging for the basic algorithm. In terms of speed and accuracy, the idea of a linearly adaptive gradient matrix presented in this paper provides an interesting compromise between a standard optimization technique that recomputes the gradient at every iteration and the fixed gradient matrix approach of the basic AAM. [ABSTRACT FROM AUTHOR]

The past 13 years have seen the development of many algorithms for approximating matrix functions in O(N) time, where N is the basis size. These O(N) algorithms rely on assumptions about the spatial locality of the matrix function; therefore their validity depends very much on the argument of the matrix function. In this article I carefully examine the validity of certain O(N) algorithms when applied to Hamiltonians of disordered systems. I focus on the prototypical disordered system, the Anderson model. I find that O(N) algorithms for the density matrix function can be used well below the Anderson transition (i.e. in the metallic phase;) they fail only when the coherence length becomes large. This paper also includes some experimental results about the Anderson model's behaviour across a range of disorders. Copyright © 2005 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

This paper discusses a special class of mathematical programs with nonlinear complementarity constraints, its goal is to present a globally and superlinearly convergent algorithm for the discussed problems. We first reformulate the complementarity constraints as a standard nonlinear equality and inequality constraints by making use of a class of generalized smoothing complementarity functions, then present a new SQP algorithm for the discussed problems. At each iteration, with the help of a pivoting operation, a master search direction is yielded by solving a quadratic program, and a correction search direction for avoiding the Maratos effect is generated by an explicit formula. Under suitable assumptions, without the strict complementarity on the upper-level inequality constraints, the proposed algorithm converges globally to a B-stationary point of the problems, and its convergence rate is superlinear. [ABSTRACT FROM AUTHOR]

This paper presents a particular construction of neighborhood matrices to be used in the computation of the interpolation weights in AMG (algebraic multigrid). The method utilizes the existence of simple interpolation matrices (piecewise constant for example) on a hierarchy of coarse spaces (grids). Then one constructs by algebraic means graded away coarse spaces for any given fine-grid neighborhood. Next, the corresponding stiffness matrix is computed on this graded away mesh, and the actual neighborhood matrix is obtained by computing the multilevel Schur complement of this matrix where degrees of freedom outside the neighborhood have to be eliminated. The paper presents algorithmic details, provides model complexity analysis as well as some comparative tests of the quality of the resulting interpolation based on the multilevel Schur complements versus element interpolation based on the true element matrices. [ABSTRACT FROM AUTHOR]

A new smoothing strategy for solving ϵ-support vector regression (ϵ-SVR), tolerating a small error in filling a given data set linearly or nonlinearly, is proposed in this paper. Conventionally, ϵ-SVR is formulated as a constrained minimization problem, namely, a convex quadratic programming problem. We apply the smoothing techniques that have been used for solving the support vector machine for classification, to replace the ϵ-insensitive loss function by an accurate smooth approximation. This will allow us to solve ϵ-SVR as an unconstrained minimization problem directly. We term this reformulated problem as ϵ-smooth support vector regression (ϵ-SSVR). We also prescribe a Newton-Armijo algorithm that has been shown to be convergent globally and quadratically to solve our ϵ-SSVR. In order to handle the case of nonlinear regression with a massive data set, we also introduce the reduced kernel technique in this paper to avoid the computational difficulties in dealing with a huge and fully dense kernel matrix. Numerical results and comparisons are given, to demonstrate the effectiveness and speed of the algorithm. [ABSTRACT FROM AUTHOR]

Many popular solution methods for large discrete ill-posed problems are based on Tikhonov regularization and compute a partial Lanczos bidiagonalization of the matrix. The computational effort required by these methods is not reduced significantly when the matrix of the discrete ill-posed problem, rather than being a general nonsymmetric matrix, is symmetric and possibly indefinite. This paper describes new methods, based on partial Lanczos tridiagonalization of the matrix, that exploit symmetry. Computed examples illustrate that one of these methods can require significantly less computational work than available structure-ignoring schemes. Copyright © 2004 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In this paper we propose a non-interior-point smoothing algorithm for solving the monotone nonlinear complementarity problem (NCP). The proposed algorithm is simpler than many existing non-interior-point smoothing algorithms in the sense that it only needs to solve one system of linear equations and to perform one line search at each iteration. We show that the proposed algorithm is globally convergent under the assumption that the NCP concerned has a nonempty solution set. Such assumption is weaker than those required by most other non-interior-point smoothing algorithms. In particular, we prove that the solution obtained by the proposed algorithm is a maximally complementary solution of the NCP concerned. Preliminary numerical results are reported. [ABSTRACT FROM AUTHOR]

In this paper, output-feedback control of continuous-time descriptor systems through a fixed-order controller is addressed. The sufficient and necessary condition for the descriptor system to be admissibly stabilizable by a fixed-order controller is given in a bilinear matrix inequality form. An iterative optimization algorithm is presented to numerically calculate the fixed-order dynamic controller. [ABSTRACT FROM AUTHOR]

This paper analyses a novel method for constructing preconditioners for diagonally dominant symmetric positive-definite matrices. The method discussed here is based on a simple idea: we construct M by simply dropping offdiagonal non-zeros from A and modifying the diagonal elements to maintain a certain row-sum property. The preconditioners are extensions of Vaidya's augmented maximum-spanning-tree preconditioners. The preconditioners presented here were also mentioned by Vaidya in an unpublished manuscript, but without a complete analysis. The preconditioners that we present have only O(n+t2) nonzeros, where n is the dimension of the matrix and 1⩽t⩽n is a parameter that one can choose. Their construction is efficient and guarantees that the condition number of the preconditioned system is O(n2/t2) if the number of nonzeros per row in the matrix is bounded by a constant. We have developed an efficient algorithm to construct these preconditioners and we have implemented it. We used our implementation to solve a simple model problem; we show the combinatorial structure of the preconditioners and we present encouraging convergence results. [ABSTRACT FROM AUTHOR]

In this paper, we develop a reduced-order modeling technique, which is based on a low-frequency expansion of the electromagnetic field. The expansion can be written in terms of the pseudoinverse of a so-called system matrix. This pseudoinverse is given explicitly, and it is shown that it satisfies a reciprocity relation. Moreover, we show that computing matrix-vector products with this pseudoinverse essentially amounts to repeatedly solving Poisson's equation. The latter two properties allow us to efficiently compute reduced-order models via a Lanczos-type algorithm. The proposed method is illustrated by a number of numerical examples. [ABSTRACT FROM AUTHOR]

Due to recent advances in the development of linear programming solvers, some of the formerly considered difficult multicommodity problems can today be solved in few minutes, even faster than with specialized methods. However, for other kind of multicommodity instances, general linear solvers can still be quite inefficient. In this paper we will give an overview of the current state-of-the-art in solving large-scale multicommodity problems, comparing an specialized interior-point algorithm with CPLEX 6.5 in the solution of difficult multicommodity problems of up lo I million of variables and 300,000 constraints. [ABSTRACT FROM AUTHOR]

Effective design of parallel matrix multiplication algorithms relies on the consideration of many interdependent issues based on the underlying parallel machine or network upon which such algorithms will be implemented, as well as, the type of methodology utilized by an algorithm. In this paper, we determine the parallel complexity of multiplying two (not necessarily square) matrices on parallel distributed-memory machines and/or networks. In other words, we provided an achievable parallel run-time that can not be beaten by any algorithm (known or unknown) for solving this problem. In addition, any algorithm that claims to be optimal must attain this run-time. In order to obtain results that are general and useful throughout a span of machines, we base our results on the well-known LogP model. Furthermore, three important criteria must be considered in order to determine the running time of a parallel algorithm; namely, (i) local computational tasks, (ii) the initial data layout, and (iii) the communication schedule. We provide optimality results by first proving general lower bounds on parallel run-time. These lower bounds lead to significant insights on (i)–(iii) above. In particular, we present what types of data layouts and communication schedules are needed in order to obtain optimal run-times. We prove that no one data layout can achieve optimal running times for all cases. Instead, optimal layouts depend on the dimensions of each matrix, and on the number of processors. Lastly, optimal algorithms are provided. [ABSTRACT FROM AUTHOR]

The implicitly shifted (bulge-chasing) QZ algorithm is the most popular method for solving the generalized eigenvalue problem Av = λBv. This paper explains why the QZ algorithm functions well even in the presence of infinite eigenvalues. The key to rapid convergence of QZ (and QR) algorithms is the effective transmission of shifts during the bulge chase. In this paper the mechanism of transmission of shifts is identified, and it is shown that this mechanism is not disrupted by the presence of infinite eigenvalues. Both the QZ algorithm and the preliminary reduction to Hessenberg-triangular form tend to push the infinite eigenvalues toward the top of the pencil. Thus they should be deflated at the top. [ABSTRACT FROM AUTHOR]

We consider the problem of approximating a given m x n matrix A by another matrix of specified rank k, which is smaller than m and n. The Singular Value Decomposition (SVD) can be used to find the "best" such approximation. However, it takes time polynomial in m, n which is prohibitive for some modern applications. In this article, we develop an algorithm that is qualitatively faster, provided we may sample the entries of the matrix in accordance with a natural probability distribution. In many applications, such sampling can be done efficiently. Our main result is a randomized algorithm to find the description of a matrix D* of rank at most k so that ... holds with probability at least 1 - δ (where ... is the Frobenius norm). The algorithm takes time polynomial in k, 1/ε log(1/δ) only and is independent of m and n. In particular, this implies that in constant time, it can be determined if a given matrix of arbitrary size has a good low-rank approximation. [ABSTRACT FROM AUTHOR]

We present a general computer algorithm to contract an arbitrary number of second-quantized expressions and simplify the obtained analytical result. The functions that perform these operations are a part of the program Nostromo which facilitates the handling and analysis of the complicated mathematical formulas which are often encountered in modern quantum-chemical models. In contrast to existing codes of this kind, Nostromo is based solely on the Goldstone-diagrammatic representation of algebraic expressions in Fock space and has capabilities to work with operators as well as scalars. Each Goldstone diagram is internally represented by a line of text which is easy to interpret and transform. The calculation of matrix elements does not exploit Wick’s theorem in a direct way, but uses diagrammatic techniques to produce only nonzero terms. The identification of equivalent expressions and their subsequent factorization in the final result is performed easily by analyzing the topological structure of the diagrammatic expressions. © 2004 American Institute of Physics. [ABSTRACT FROM AUTHOR]

Structured matrices are encountered in various guises in many mathematical models which describe problems of the real world. In fact, they are the algebraic translation of the specific properties at the basis of the physical problem. The analysis and the exploitation of matrix structures is the first fundamental step in the design of highly efficient algorithms for the solution of complex computational problems. [ABSTRACT FROM AUTHOR]