Based on a new efficient identification technique of active constraints introduced in this paper, a new sequential systems of linear equations (SSLE) algorithm generating feasible iterates is proposed for solving no...Based on a new efficient identification technique of active constraints introduced in this paper, a new sequential systems of linear equations (SSLE) algorithm generating feasible iterates is proposed for solving nonlinear optimization problems with inequality constraints. In this paper, we introduce a new technique for constructing the system of linear equations, which recurs to a perturbation for the gradients of the constraint functions. At each iteration of the new algorithm, a feasible descent direction is obtained by solving only one system of linear equations without doing convex combination. To ensure the global convergence and avoid the Maratos effect, the algorithm needs to solve two additional reduced systems of linear equations with the same coefficient matrix after finite iterations. The proposed algorithm is proved to be globally and superlinearly convergent under some mild conditions. What distinguishes this algorithm from the previous feasible SSLE algorithms is that an improving direction is obtained easily and the computation cost of generating a new iterate is reduced. Finally, a preliminary implementation has been tested.展开更多
Presents information on a study which proposed a superlinearly convergent algorithm of sequential systems of linear equations or nonlinear optimization problems with inequality constraints. Assumptions; Discussion on ...Presents information on a study which proposed a superlinearly convergent algorithm of sequential systems of linear equations or nonlinear optimization problems with inequality constraints. Assumptions; Discussion on lemmas about several matrices related to the common coefficient matrix F; Strengthening of the regularity assumptions on the functions involved; Numerical experiments.展开更多
Fundamental matrix operations and solving linear systems of equations are ubiquitous in scientific investigations.Using the‘sender-receiver’model,we propose quantum algorithms for matrix operations such as matrix-ve...Fundamental matrix operations and solving linear systems of equations are ubiquitous in scientific investigations.Using the‘sender-receiver’model,we propose quantum algorithms for matrix operations such as matrix-vector product,matrix-matrix product,the sum of two matrices,and the calculation of determinant and inverse matrix.We encode the matrix entries into the probability amplitudes of the pure initial states of senders.After applying proper unitary transformation to the complete quantum system,the desired result can be found in certain blocks of the receiver’s density matrix.These quantum protocols can be used as subroutines in other quantum schemes.Furthermore,we present an alternative quantum algorithm for solving linear systems of equations.展开更多
Variational quantum algorithms are promising methods with the greatest potential to achieve quantum advantage,widely employed in the era of noisy intermediate-scale quantum computing.This study presents an advanced va...Variational quantum algorithms are promising methods with the greatest potential to achieve quantum advantage,widely employed in the era of noisy intermediate-scale quantum computing.This study presents an advanced variational hybrid algorithm(EVQLSE)that leverages both quantum and classical computing paradigms to address the solution of linear equation systems.Initially,an innovative loss function is proposed,drawing inspiration from the similarity measure between two quantum states.This function exhibits a substantial improvement in computational complexity when benchmarked against the variational quantum linear solver.Subsequently,a specialized parameterized quantum circuit structure is presented for small-scale linear systems,which exhibits powerful expressive capabilities.Through rigorous numerical analysis,the expressiveness of this circuit structure is quantitatively assessed using a variational quantum regression algorithm,and it obtained the best score compared to the others.Moreover,the expansion in system size is accompanied by an increase in the number of parameters,placing considerable strain on the training process for the algorithm.To address this challenge,an optimization strategy known as quantum parameter sharing is introduced,which proficiently minimizes parameter volume while adhering to exacting precision standards.Finally,EVQLSE is successfully implemented on a quantum computing platform provided by IBM for the resolution of large-scale problems characterized by a dimensionality of 220.展开更多
This paper gives and proofs a theorem, for any matrix A, do elementary column operations, change it to a matrix which is partitioned to two blocks which left one is column full rank and right one is zero matrix. That ...This paper gives and proofs a theorem, for any matrix A, do elementary column operations, change it to a matrix which is partitioned to two blocks which left one is column full rank and right one is zero matrix. That is, use a invertible matrix P to let AP = (B,O), O is zero matrix with n-r columns, r and n is rank and column number of A, so the P's right n-r columns is just the basis of the null space of the matrix A. On the basis of the theorem, lots of problems of linear algebra can be resolved and lots of theorems can be proofed by elementary column operations. Perhaps the textbooks used in universities will have a lot of change with the result of the paper. This result is first found by author in 2010.12.8 in http://www.paper.edu.cn/index.php/default/releasepaper/content/201012-232, but is not formal published.展开更多
This paper proposes a parallel algorithm, called KDOP (K-DimensionalOptimal Parallel algorithm), to solve a general class of recurrence equations efficiently. The KDOP algorithm partitions the computation into a serie...This paper proposes a parallel algorithm, called KDOP (K-DimensionalOptimal Parallel algorithm), to solve a general class of recurrence equations efficiently. The KDOP algorithm partitions the computation into a series of sub-computations, each of which is executed in the fashion that all the processors work simultaneously with each one executing an optimal sequential algorithm to solve a subcomputation task. The algorithm solves the equations in O(N/p)steps in EREW PRAM model (Exclusive Read Exclusive Write Parallel Ran-dom Access Machine model) using p<N1-e processors, where N is the size of the problem, and e is a given constant. This is an optimal algorithm (itsspeedup is O(p)) in the case of p<N1-e. Such an optimal speedup for this problem was previously achieved only in the case of p<N0.5. The algorithm can be implemented on machines with multiple processing elements or pipelined vector machines with parallel memory systems.展开更多
For the large sparse systems of linear and nonlinear equations, a new class of generalized asynchronous parallel multisplitting iterative method is presented, and its convergence theory is established under suitable c...For the large sparse systems of linear and nonlinear equations, a new class of generalized asynchronous parallel multisplitting iterative method is presented, and its convergence theory is established under suitable conditions. This method not only unifies the discussions of various existing asynchronous multisplitting iterations, but also affords new algorithmic and theoretical results for the parallel solution of large sparse system of linear equations. Besides its generality, this method is also much more suitable for implementing on the MIMD multiprocessor systems.展开更多
基金Supported by National Natural Science Foundation of China (Grant No. 10771040)Guangxi Science Foundation (Grant No. 0832052)Guangxi University for Nationalities Youth Foundation (Grant No. 2007QN24)
文摘Based on a new efficient identification technique of active constraints introduced in this paper, a new sequential systems of linear equations (SSLE) algorithm generating feasible iterates is proposed for solving nonlinear optimization problems with inequality constraints. In this paper, we introduce a new technique for constructing the system of linear equations, which recurs to a perturbation for the gradients of the constraint functions. At each iteration of the new algorithm, a feasible descent direction is obtained by solving only one system of linear equations without doing convex combination. To ensure the global convergence and avoid the Maratos effect, the algorithm needs to solve two additional reduced systems of linear equations with the same coefficient matrix after finite iterations. The proposed algorithm is proved to be globally and superlinearly convergent under some mild conditions. What distinguishes this algorithm from the previous feasible SSLE algorithms is that an improving direction is obtained easily and the computation cost of generating a new iterate is reduced. Finally, a preliminary implementation has been tested.
基金This research was supported by the National Natural Science Foundation of China(19571001, 19971002, 79970014) Cross-century Excellent Personnel Award and Teaching and Research Award Program for Outstanding Young Teachers in High Education Ministry o
文摘Presents information on a study which proposed a superlinearly convergent algorithm of sequential systems of linear equations or nonlinear optimization problems with inequality constraints. Assumptions; Discussion on lemmas about several matrices related to the common coefficient matrix F; Strengthening of the regularity assumptions on the functions involved; Numerical experiments.
基金supported by the National Natural Science Foundation of China(Grant No.12031004 and Grant No.12271474,61877054)the Fundamental Research Foundation for the Central Universities(Project No.K20210337)+1 种基金the Zhejiang University Global Partnership Fund,188170+194452119/003partially funded by a state task of Russian Fundamental Investigations(State Registration No.FFSG-2024-0002)。
文摘Fundamental matrix operations and solving linear systems of equations are ubiquitous in scientific investigations.Using the‘sender-receiver’model,we propose quantum algorithms for matrix operations such as matrix-vector product,matrix-matrix product,the sum of two matrices,and the calculation of determinant and inverse matrix.We encode the matrix entries into the probability amplitudes of the pure initial states of senders.After applying proper unitary transformation to the complete quantum system,the desired result can be found in certain blocks of the receiver’s density matrix.These quantum protocols can be used as subroutines in other quantum schemes.Furthermore,we present an alternative quantum algorithm for solving linear systems of equations.
基金supported by the National Natural Science Foundation of China under Grant Nos.62172268 and 62302289the Shanghai Science and Technology Project under Grant Nos.21JC1402800 and 23YF1416200。
文摘Variational quantum algorithms are promising methods with the greatest potential to achieve quantum advantage,widely employed in the era of noisy intermediate-scale quantum computing.This study presents an advanced variational hybrid algorithm(EVQLSE)that leverages both quantum and classical computing paradigms to address the solution of linear equation systems.Initially,an innovative loss function is proposed,drawing inspiration from the similarity measure between two quantum states.This function exhibits a substantial improvement in computational complexity when benchmarked against the variational quantum linear solver.Subsequently,a specialized parameterized quantum circuit structure is presented for small-scale linear systems,which exhibits powerful expressive capabilities.Through rigorous numerical analysis,the expressiveness of this circuit structure is quantitatively assessed using a variational quantum regression algorithm,and it obtained the best score compared to the others.Moreover,the expansion in system size is accompanied by an increase in the number of parameters,placing considerable strain on the training process for the algorithm.To address this challenge,an optimization strategy known as quantum parameter sharing is introduced,which proficiently minimizes parameter volume while adhering to exacting precision standards.Finally,EVQLSE is successfully implemented on a quantum computing platform provided by IBM for the resolution of large-scale problems characterized by a dimensionality of 220.
文摘This paper gives and proofs a theorem, for any matrix A, do elementary column operations, change it to a matrix which is partitioned to two blocks which left one is column full rank and right one is zero matrix. That is, use a invertible matrix P to let AP = (B,O), O is zero matrix with n-r columns, r and n is rank and column number of A, so the P's right n-r columns is just the basis of the null space of the matrix A. On the basis of the theorem, lots of problems of linear algebra can be resolved and lots of theorems can be proofed by elementary column operations. Perhaps the textbooks used in universities will have a lot of change with the result of the paper. This result is first found by author in 2010.12.8 in http://www.paper.edu.cn/index.php/default/releasepaper/content/201012-232, but is not formal published.
文摘This paper proposes a parallel algorithm, called KDOP (K-DimensionalOptimal Parallel algorithm), to solve a general class of recurrence equations efficiently. The KDOP algorithm partitions the computation into a series of sub-computations, each of which is executed in the fashion that all the processors work simultaneously with each one executing an optimal sequential algorithm to solve a subcomputation task. The algorithm solves the equations in O(N/p)steps in EREW PRAM model (Exclusive Read Exclusive Write Parallel Ran-dom Access Machine model) using p<N1-e processors, where N is the size of the problem, and e is a given constant. This is an optimal algorithm (itsspeedup is O(p)) in the case of p<N1-e. Such an optimal speedup for this problem was previously achieved only in the case of p<N0.5. The algorithm can be implemented on machines with multiple processing elements or pipelined vector machines with parallel memory systems.
文摘For the large sparse systems of linear and nonlinear equations, a new class of generalized asynchronous parallel multisplitting iterative method is presented, and its convergence theory is established under suitable conditions. This method not only unifies the discussions of various existing asynchronous multisplitting iterations, but also affords new algorithmic and theoretical results for the parallel solution of large sparse system of linear equations. Besides its generality, this method is also much more suitable for implementing on the MIMD multiprocessor systems.