An optimal parallel algorithm for sparse matrix bandwidth reduction on a linear array

A simple and efficient algorithm for the bandwidth reduction of sparse symmetric matrices is proposed. It involves column-row permutations and is well-suited to map onto the linear array topology of the SIMD architectures. The efficiency of the algorithm is compared with the other existing algorithms. The interconnectivity and the memory requirement of the linear array are discussed and the complexity of its layout area is derived. The parallel version of the algorithm mapped onto the linear array is then introduced and is explained with the help of an example. The optimality of the parallel algorithm is proved by deriving the time complexities of the algorithm on a single processor and the linear array.

Low-rank optimization on the cone of positive semidefinite matrices

We propose an algorithm for solving optimization problems defined on a subset of the cone of symmetric positive semidefinite matrices. This algorithm relies on the factorization X = Y Y T , where the number of columns of Y fixes an upper bound on the rank of the positive semidefinite matrix X. It is thus very effective for solving problems that have a low-rank solution. The factorization X = Y Y T leads to a reformulation of the original problem as an optimization on a particular quotient manifold. The present paper discusses the geometry of that manifold and derives a second-order optimization method with guaranteed quadratic convergence. It furthermore provides some conditions on the rank of the factorization to ensure equivalence with the original problem. In contrast to existing methods, the proposed algorithm converges monotonically to the sought solution. Its numerical efficiency is evaluated on two applications: the maximal cut of a graph and the problem of sparse principal component analysis. © 2010 Society for Industrial and Applied Mathematics.

Low rank representation on Riemannian manifold of symmetric positive definite matrices

Sparse coding aims to find a more compact representation based on a set of dictionary atoms. A well-known technique looking at 2D sparsity is the low rank representation (LRR). However, in many computer vision applications, data often originate from a manifold, which is equipped with some Riemannian geometry. In this case, the existing LRR becomes inappropriate for modeling and incorporating the intrinsic geometry of the manifold that is potentially important and critical to applications. In this paper, we generalize the LRR over the Euclidean space to the LRR model over a specific Rimannian manifold—the manifold of symmetric positive matrices (SPD). Experiments on several computer vision datasets showcase its noise robustness and superior performance on classification and segmentation compared with state-of-the-art approaches.

Stabilized sparse ordinal regression for medical risk stratification

The recent wide adoption of electronic medical records (EMRs) presents great opportunities and challenges for data mining. The EMR data are largely temporal, often noisy, irregular and high dimensional. This paper constructs a novel ordinal regression framework for predicting medical risk stratification from EMR. First, a conceptual view of EMR as a temporal image is constructed to extract a diverse set of features. Second, ordinal modeling is applied for predicting cumulative or progressive risk. The challenges are building a transparent predictive model that works with a large number of weakly predictive features, and at the same time, is stable against resampling variations. Our solution employs sparsity methods that are stabilized through domain-specific feature interaction networks. We introduces two indices that measure the model stability against data resampling. Feature networks are used to generate two multivariate Gaussian priors with sparse precision matrices (the Laplacian and Random Walk). We apply the framework on a large short-term suicide risk prediction problem and demonstrate that our methods outperform clinicians to a large margin, discover suicide risk factors that conform with mental health knowledge, and produce models with enhanced stability. © 2014 Springer-Verlag London.

Matrix-vector multiplication and triangular linear solver using GPGPU for symmetric positive definite matrices derived from elliptic equations

The modern GPUs are well suited for intensive computational tasks and massive parallel computation. Sparse matrix multiplication and linear triangular solver are the most important and heavily used kernels in scientific computation, and several challenges in developing a high performance kernel with the two modules is investigated. The main interest it to solve linear systems derived from the elliptic equations with triangular elements. The resulting linear system has a symmetric positive definite matrix. The sparse matrix is stored in the compressed sparse row (CSR) format. It is proposed a CUDA algorithm to execute the matrix vector multiplication using directly the CSR format. A dependence tree algorithm is used to determine which variables the linear triangular solver can determine in parallel. To increase the number of the parallel threads, a coloring graph algorithm is implemented to reorder the mesh numbering in a pre-processing phase. The proposed method is compared with parallel and serial available libraries. The results show that the proposed method improves the computation cost of the matrix vector multiplication. The pre-processing associated with the triangular solver needs to be executed just once in the proposed method. The conjugate gradient method was implemented and showed similar convergence rate for all the compared methods. The proposed method showed significant smaller execution time.

Linear Sparse Differential Resultant Formulas

Let P be a system of n linear nonhomogeneous ordinary differential polynomials in a set U of n-1 differential indeterminates. Differential resultant formulas are presented to eliminate the differential indeterminates in U from P. These formulas are determinants of coefficient matrices of appropriate sets of derivatives of the differential polynomials in P, or in a linear perturbation Pe of P. In particular, the formula dfres(P) is the determinant of a matrix M(P) having no zero columns if the system P is ``super essential". As an application, if the system PP is sparse generic, such formulas can be used to compute the differential resultant dres(PP) introduced by Li, Gao and Yuan.

Differential elimination by differential specialization of Sylvester style matrices

Differential resultant formulas are defined, for a system $\cP$ of $n$ ordinary Laurent differential polynomials in $n-1$ differential variables. These are determinants of coefficient matrices of an extended system of polynomials obtained from $\cP$ through derivations and multiplications by Laurent monomials. To start, through derivations, a system $\ps(\cP)$ of $L$ polynomials in $L-1$ algebraic variables is obtained, which is non sparse in the order of derivation. This enables the use of existing formulas for the computation of algebraic resultants, of the multivariate sparse algebraic polynomials in $\ps(\cP)$, to obtain polynomials in the differential elimination ideal generated by $\cP$. The formulas obtained are multiples of the sparse differential resultant defined by Li, Yuan and Gao, and provide order and degree bounds in terms of mixed volumes in the generic case.

Sparse matrix inversion,

Mode of access: Internet.

A Numerical Solution Using an Adaptively Preconditioned Lanczos Method for a Class of Linear Systems Related with the Fractional Poisson Equation

This study considers the solution of a class of linear systems related with the fractional Poisson equation (FPE) (−∇2)α/2φ=g(x,y) with nonhomogeneous boundary conditions on a bounded domain. A numerical approximation to FPE is derived using a matrix representation of the Laplacian to generate a linear system of equations with its matrix A raised to the fractional power α/2. The solution of the linear system then requires the action of the matrix function f(A)=A−α/2 on a vector b. For large, sparse, and symmetric positive definite matrices, the Lanczos approximation generates f(A)b≈β0Vmf(Tm)e1. This method works well when both the analytic grade of A with respect to b and the residual for the linear system are sufficiently small. Memory constraints often require restarting the Lanczos decomposition; however this is not straightforward in the context of matrix function approximation. In this paper, we use the idea of thick-restart and adaptive preconditioning for solving linear systems to improve convergence of the Lanczos approximation. We give an error bound for the new method and illustrate its role in solving FPE. Numerical results are provided to gauge the performance of the proposed method relative to exact analytic solutions.

Addressing issues in sparseness, ecological bias and formulation of the adjacency matrix in Bayesian spatio-temporal analysis of disease counts

The main objective of this PhD was to further develop Bayesian spatio-temporal models (specifically the Conditional Autoregressive (CAR) class of models), for the analysis of sparse disease outcomes such as birth defects. The motivation for the thesis arose from problems encountered when analyzing a large birth defect registry in New South Wales. The specific components and related research objectives of the thesis were developed from gaps in the literature on current formulations of the CAR model, and health service planning requirements. Data from a large probabilistically-linked database from 1990 to 2004, consisting of fields from two separate registries: the Birth Defect Registry (BDR) and Midwives Data Collection (MDC) were used in the analyses in this thesis. The main objective was split into smaller goals. The first goal was to determine how the specification of the neighbourhood weight matrix will affect the smoothing properties of the CAR model, and this is the focus of chapter 6. Secondly, I hoped to evaluate the usefulness of incorporating a zero-inflated Poisson (ZIP) component as well as a shared-component model in terms of modeling a sparse outcome, and this is carried out in chapter 7. The third goal was to identify optimal sampling and sample size schemes designed to select individual level data for a hybrid ecological spatial model, and this is done in chapter 8. Finally, I wanted to put together the earlier improvements to the CAR model, and along with demographic projections, provide forecasts for birth defects at the SLA level. Chapter 9 describes how this is done. For the first objective, I examined a series of neighbourhood weight matrices, and showed how smoothing the relative risk estimates according to similarity by an important covariate (i.e. maternal age) helped improve the model’s ability to recover the underlying risk, as compared to the traditional adjacency (specifically the Queen) method of applying weights. Next, to address the sparseness and excess zeros commonly encountered in the analysis of rare outcomes such as birth defects, I compared a few models, including an extension of the usual Poisson model to encompass excess zeros in the data. This was achieved via a mixture model, which also encompassed the shared component model to improve on the estimation of sparse counts through borrowing strength across a shared component (e.g. latent risk factor/s) with the referent outcome (caesarean section was used in this example). Using the Deviance Information Criteria (DIC), I showed how the proposed model performed better than the usual models, but only when both outcomes shared a strong spatial correlation. The next objective involved identifying the optimal sampling and sample size strategy for incorporating individual-level data with areal covariates in a hybrid study design. I performed extensive simulation studies, evaluating thirteen different sampling schemes along with variations in sample size. This was done in the context of an ecological regression model that incorporated spatial correlation in the outcomes, as well as accommodating both individual and areal measures of covariates. Using the Average Mean Squared Error (AMSE), I showed how a simple random sample of 20% of the SLAs, followed by selecting all cases in the SLAs chosen, along with an equal number of controls, provided the lowest AMSE. The final objective involved combining the improved spatio-temporal CAR model with population (i.e. women) forecasts, to provide 30-year annual estimates of birth defects at the Statistical Local Area (SLA) level in New South Wales, Australia. The projections were illustrated using sixteen different SLAs, representing the various areal measures of socio-economic status and remoteness. A sensitivity analysis of the assumptions used in the projection was also undertaken. By the end of the thesis, I will show how challenges in the spatial analysis of rare diseases such as birth defects can be addressed, by specifically formulating the neighbourhood weight matrix to smooth according to a key covariate (i.e. maternal age), incorporating a ZIP component to model excess zeros in outcomes and borrowing strength from a referent outcome (i.e. caesarean counts). An efficient strategy to sample individual-level data and sample size considerations for rare disease will also be presented. Finally, projections in birth defect categories at the SLA level will be made.

Urban dynamic origin-destination matrices estimation

The aim of this paper is to explore a new approach to obtain better traffic demand (Origin-Destination, OD matrices) for dense urban networks. From reviewing existing methods, from static to dynamic OD matrix evaluation, possible deficiencies in the approach could be identified: traffic assignment details for complex urban network and lacks in dynamic approach. To improve the global process of traffic demand estimation, this paper is focussing on a new methodology to determine dynamic OD matrices for urban areas characterized by complex route choice situation and high level of traffic controls. An iterative bi-level approach will be used, the Lower level (traffic assignment) problem will determine, dynamically, the utilisation of the network by vehicles using heuristic data from mesoscopic traffic simulator and the Upper level (matrix adjustment) problem will proceed to an OD estimation using optimization Kalman filtering technique. In this way, a full dynamic and continuous estimation of the final OD matrix could be obtained. First results of the proposed approach and remarks are presented.

Mineralized human primary osteoblast matrices as a model system to analyse interactions of prostate cancer cells with the bone microenvironment

Prostate cancer metastasis is reliant on the reciprocal interactions between cancer cells and the bone niche/micro-environment. The production of suitable matrices to study metastasis, carcinogenesis and in particular prostate cancer/bone micro-environment interaction has been limited to specific protein matrices or matrix secreted by immortalised cell lines that may have undergone transformation processes altering signaling pathways and modifying gene or receptor expression. We hypothesize that matrices produced by primary human osteoblasts are a suitable means to develop an in vitro model system for bone metastasis research mimicking in vivo conditions. We have used a decellularized matrix secreted from primary human osteoblasts as a model for prostate cancer function in the bone micro-environment. We show that this collagen I rich matrix is of fibrillar appearance, highly mineralized, and contains proteins, such as osteocalcin, osteonectin and osteopontin, and growth factors characteristic of bone extracellular matrix (ECM). LNCaP and PC3 cells grown on this matrix, adhere strongly, proliferate, and express markers consistent with a loss of epithelial phenotype. Moreover, growth of these cells on the matrix is accompanied by the induction of genes associated with attachment, migration, increased invasive potential, Ca2+ signaling and osteolysis. In summary, we show that growth of prostate cancer cells on matrices produced by primary human osteoblasts mimics key features of prostate cancer bone metastases and thus is a suitable model system to study the tumor/bone micro-environment interaction in this disease.

Osteogenic induction of human bone marrow-derived mesenchymal progenitor cells in novel synthetic polymer-hydrogel matrices

The aim of this project was to investigate the in vitro osteogenic potential of human mesenchymal progenitor cells in novel matrix architectures built by means of a three-dimensional bioresorbable synthetic framework in combination with a hydrogel. Human mesenchymal progenitor cells (hMPCs) were isolated from a human bone marrow aspirate by gradient centrifugation. Before in vitro engineering of scaffold-hMPC constructs, the adipogenic and osteogenic differentiation potential was demonstrated by staining of neutral lipids and induction of bone-specific proteins, respectively. After expansion in monolayer cultures, the cells were enzymatically detached and then seeded in combination with a hydrogel into polycaprolactone (PCL) and polycaprolactone-hydroxyapatite (PCL-HA) frameworks. This scaffold design concept is characterized by novel matrix architecture, good mechanical properties, and slow degradation kinetics of the framework and a biomimetic milieu for cell delivery and proliferation. To induce osteogenic differentiation, the specimens were cultured in an osteogenic cell culture medium and were maintained in vitro for 6 weeks. Cellular distribution and viability within three-dimensional hMPC bone grafts were documented by scanning electron microscopy, cell metabolism assays, and confocal laser microscopy. Secretion of the osteogenic marker molecules type I procollagen and osteocalcin was analyzed by semiquantitative immunocytochemistry assays. Alkaline phosphatase activity was visualized by p-nitrophenyl phosphate substrate reaction. During osteogenic stimulation, hMPCs proliferated toward and onto the PCL and PCL-HA scaffold surfaces and metabolic activity increased, reaching a plateau by day 15. The temporal pattern of bone-related marker molecules produced by in vitro tissue-engineered scaffold-cell constructs revealed that hMPCs differentiated better within the biomimetic matrix architecture along the osteogenic lineage.

In vitro characterization of natural and synthetic dermal matrices cultured with human dermal fibroblasts

The ideal dermal matrix should be able to provide the right biological and physical environment to ensure homogenous cell and extracellular matrix (ECM) distribution, as well as the right size and morphology of the neo-tissue required. Four natural and synthetic 3D matrices were evaluated in vitro as dermal matrices, namely (1) equine collagen foam, TissuFleece®, (2) acellular dermal replacement, Alloderm®, (3) knitted poly(lactic-co-glycolic acid) (10:90)–poly(-caprolactone) (PLGA–PCL) mesh, (4) chitosan scaffold. Human dermal fibroblasts were cultured on the specimens over 3 weeks. Cell morphology, distribution and viability were assessed by electron microscopy, histology and confocal laser microscopy. Metabolic activity and DNA synthesis were analysed via MTS metabolic assay and [3H]-thymidine uptake, while ECM protein expression was determined by immunohistochemistry. TissuFleece®, Alloderm® and PLGA–PCL mesh supported cell attachment, proliferation and neo-tissue formation. However, TissuFleece® contracted to 10% of the original size while Alloderm® supported cell proliferation predominantly on the surface of the material. PLGA–PCL mesh promoted more homogenous cell distribution and tissue formation. Chitosan scaffolds did not support cell attachment and proliferation. These results demonstrated that physical characteristics including porosity and mechanical stability to withstand cell contraction forces are important in determining the success of a dermal matrix material.