Toeplitz matrix-vector multiplication is widely used in various fields,including optimal control,systolic finite field multipliers,multidimensional convolution,etc.In this paper,we first present a non-asymptotic quant...Toeplitz matrix-vector multiplication is widely used in various fields,including optimal control,systolic finite field multipliers,multidimensional convolution,etc.In this paper,we first present a non-asymptotic quantum algorithm for Toeplitz matrix-vector multiplication with time complexity O(κpolylogn),whereκand 2n are the condition number and the dimension of the circulant matrix extended from the Toeplitz matrix,respectively.For the case with an unknown generating function,we also give a corresponding non-asymptotic quantum version that eliminates the dependency on the L_(1)-normρof the displacement of the structured matrices.Due to the good use of the special properties of Toeplitz matrices,the proposed quantum algorithms are sufficiently accurate and efficient compared to the existing quantum algorithms under certain circumstances.展开更多
As one of the most essential and important operations in linear algebra, the performance prediction of sparse matrix-vector multiplication (SpMV) on GPUs has got more and more attention in recent years. In 2012, Guo a...As one of the most essential and important operations in linear algebra, the performance prediction of sparse matrix-vector multiplication (SpMV) on GPUs has got more and more attention in recent years. In 2012, Guo and Wang put forward a new idea to predict the performance of SpMV on GPUs. However, they didn’t consider the matrix structure completely, so the execution time predicted by their model tends to be inaccurate for general sparse matrix. To address this problem, we proposed two new similar models, which take into account the structure of the matrices and make the performance prediction model more accurate. In addition, we predict the execution time of SpMV for CSR-V, CSR-S, ELL and JAD sparse matrix storage formats by the new models on the CUDA platform. Our experimental results show that the accuracy of prediction by our models is 1.69 times better than Guo and Wang’s model on average for most general matrices.展开更多
As an important computing operation,photonic matrix-vector multiplication is widely used in photonic neutral networks and signal processing.However,conventional incoherent matrix-vector multiplication focuses on real-...As an important computing operation,photonic matrix-vector multiplication is widely used in photonic neutral networks and signal processing.However,conventional incoherent matrix-vector multiplication focuses on real-valued operations,which cannot work well in complex-valued neural networks and discrete Fourier transform.In this paper,we propose a systematic solution to extend the matrix computation of microring arrays from the real-valued field to the complex-valued field,and from small-scale(i.e.,4×4)to large-scale matrix computation(i.e.,16×16).Combining matrix decomposition and matrix partition,our photonic complex matrix-vector multiplier chip can support arbitrary large-scale and complex-valued matrix computation.We further demonstrate Walsh-Hardmard transform,discrete cosine transform,discrete Fourier transform,and image convolutional processing.Our scheme provides a path towards breaking the limits of complex-valued computing accelerator in conventional incoherent optical architecture.More importantly,our results reveal that an integrated photonic platform is of huge potential for large-scale,complex-valued,artificial intelligence computing and signal processing.展开更多
基金supported by the National Natural Science Foundation of China(Grant Nos.62071015 and 62171264)。
文摘Toeplitz matrix-vector multiplication is widely used in various fields,including optimal control,systolic finite field multipliers,multidimensional convolution,etc.In this paper,we first present a non-asymptotic quantum algorithm for Toeplitz matrix-vector multiplication with time complexity O(κpolylogn),whereκand 2n are the condition number and the dimension of the circulant matrix extended from the Toeplitz matrix,respectively.For the case with an unknown generating function,we also give a corresponding non-asymptotic quantum version that eliminates the dependency on the L_(1)-normρof the displacement of the structured matrices.Due to the good use of the special properties of Toeplitz matrices,the proposed quantum algorithms are sufficiently accurate and efficient compared to the existing quantum algorithms under certain circumstances.
文摘As one of the most essential and important operations in linear algebra, the performance prediction of sparse matrix-vector multiplication (SpMV) on GPUs has got more and more attention in recent years. In 2012, Guo and Wang put forward a new idea to predict the performance of SpMV on GPUs. However, they didn’t consider the matrix structure completely, so the execution time predicted by their model tends to be inaccurate for general sparse matrix. To address this problem, we proposed two new similar models, which take into account the structure of the matrices and make the performance prediction model more accurate. In addition, we predict the execution time of SpMV for CSR-V, CSR-S, ELL and JAD sparse matrix storage formats by the new models on the CUDA platform. Our experimental results show that the accuracy of prediction by our models is 1.69 times better than Guo and Wang’s model on average for most general matrices.
基金This work was partially supported by the National Key Research and Development Project of China(No.2018YFB2201901)the National Natural Science Foundation of China(Grant Nos.61805090 and 62075075)+1 种基金Shenzhen Science and Technology Innovation Commission(No.SGDX2019081623060558)Research Grants Council of Hong Kong SAR(No.PolyU152241/18E).
文摘As an important computing operation,photonic matrix-vector multiplication is widely used in photonic neutral networks and signal processing.However,conventional incoherent matrix-vector multiplication focuses on real-valued operations,which cannot work well in complex-valued neural networks and discrete Fourier transform.In this paper,we propose a systematic solution to extend the matrix computation of microring arrays from the real-valued field to the complex-valued field,and from small-scale(i.e.,4×4)to large-scale matrix computation(i.e.,16×16).Combining matrix decomposition and matrix partition,our photonic complex matrix-vector multiplier chip can support arbitrary large-scale and complex-valued matrix computation.We further demonstrate Walsh-Hardmard transform,discrete cosine transform,discrete Fourier transform,and image convolutional processing.Our scheme provides a path towards breaking the limits of complex-valued computing accelerator in conventional incoherent optical architecture.More importantly,our results reveal that an integrated photonic platform is of huge potential for large-scale,complex-valued,artificial intelligence computing and signal processing.
