A low-computation-complexity, energy-efficient, and high-performance linear program solver based on primal–dual interior point method using memristor crossbars

Ruizhe Cai, Ao Ren, Sucheta Soundarajan, Yanzhi Wang

Research output: Contribution to journalArticle

Abstract

Linear programming is required in a wide variety of application including routing, scheduling, and various optimization problems. The primal–dual interior point (PDIP) method is state-of-the-art algorithm for solving linear programs, and can be decomposed to matrix–vector multiplication and solving systems of linear equations, both of which can be conducted by the emerging memristor crossbar technique in O(1) time complexity in the analog domain. This work is the first to apply memristor crossbar for linear program solving based on the PDIP method, which has been reformulated for memristor crossbars to compute in the analog domain. The proposed linear program solver can overcome limitations of memristor crossbars such as supporting only non-negative coefficients, and has been extended for higher scalability. The proposed solver is iterative and achieves O(N) computation complexity in each iteration. Experimental results demonstrate that reliable performance with high accuracy can be achieved under process variations.

Original languageEnglish (US)
JournalNano Communication Networks
DOIs
StateAccepted/In press - Jan 1 2018

Fingerprint

Memristors
Interior Point Method
Energy Efficient
Linear Program
High Performance
Analogue
Process Variation
System of Linear Equations
Time Complexity
Linear programming
Scalability
Multiplication
High Accuracy
Routing
Linear equations
Non-negative
Scheduling
Optimization Problem
Iteration
Experimental Results

Keywords

  • Linear programming
  • Memristor
  • Memristor crossbar
  • Primal–dual interior point method

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Applied Mathematics
  • Electrical and Electronic Engineering

Cite this

@article{39c4c7656ac24e22aaaca5e81f003d37,
title = "A low-computation-complexity, energy-efficient, and high-performance linear program solver based on primal–dual interior point method using memristor crossbars",
abstract = "Linear programming is required in a wide variety of application including routing, scheduling, and various optimization problems. The primal–dual interior point (PDIP) method is state-of-the-art algorithm for solving linear programs, and can be decomposed to matrix–vector multiplication and solving systems of linear equations, both of which can be conducted by the emerging memristor crossbar technique in O(1) time complexity in the analog domain. This work is the first to apply memristor crossbar for linear program solving based on the PDIP method, which has been reformulated for memristor crossbars to compute in the analog domain. The proposed linear program solver can overcome limitations of memristor crossbars such as supporting only non-negative coefficients, and has been extended for higher scalability. The proposed solver is iterative and achieves O(N) computation complexity in each iteration. Experimental results demonstrate that reliable performance with high accuracy can be achieved under process variations.",
keywords = "Linear programming, Memristor, Memristor crossbar, Primal–dual interior point method",
author = "Ruizhe Cai and Ao Ren and Sucheta Soundarajan and Yanzhi Wang",
year = "2018",
month = "1",
day = "1",
doi = "10.1016/j.nancom.2018.01.001",
language = "English (US)",
journal = "Nano Communication Networks",
issn = "1878-7789",
publisher = "Elsevier",

}

TY - JOUR

T1 - A low-computation-complexity, energy-efficient, and high-performance linear program solver based on primal–dual interior point method using memristor crossbars

AU - Cai, Ruizhe

AU - Ren, Ao

AU - Soundarajan, Sucheta

AU - Wang, Yanzhi

PY - 2018/1/1

Y1 - 2018/1/1

N2 - Linear programming is required in a wide variety of application including routing, scheduling, and various optimization problems. The primal–dual interior point (PDIP) method is state-of-the-art algorithm for solving linear programs, and can be decomposed to matrix–vector multiplication and solving systems of linear equations, both of which can be conducted by the emerging memristor crossbar technique in O(1) time complexity in the analog domain. This work is the first to apply memristor crossbar for linear program solving based on the PDIP method, which has been reformulated for memristor crossbars to compute in the analog domain. The proposed linear program solver can overcome limitations of memristor crossbars such as supporting only non-negative coefficients, and has been extended for higher scalability. The proposed solver is iterative and achieves O(N) computation complexity in each iteration. Experimental results demonstrate that reliable performance with high accuracy can be achieved under process variations.

AB - Linear programming is required in a wide variety of application including routing, scheduling, and various optimization problems. The primal–dual interior point (PDIP) method is state-of-the-art algorithm for solving linear programs, and can be decomposed to matrix–vector multiplication and solving systems of linear equations, both of which can be conducted by the emerging memristor crossbar technique in O(1) time complexity in the analog domain. This work is the first to apply memristor crossbar for linear program solving based on the PDIP method, which has been reformulated for memristor crossbars to compute in the analog domain. The proposed linear program solver can overcome limitations of memristor crossbars such as supporting only non-negative coefficients, and has been extended for higher scalability. The proposed solver is iterative and achieves O(N) computation complexity in each iteration. Experimental results demonstrate that reliable performance with high accuracy can be achieved under process variations.

KW - Linear programming

KW - Memristor

KW - Memristor crossbar

KW - Primal–dual interior point method

UR - http://www.scopus.com/inward/record.url?scp=85054125564&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85054125564&partnerID=8YFLogxK

U2 - 10.1016/j.nancom.2018.01.001

DO - 10.1016/j.nancom.2018.01.001

M3 - Article

JO - Nano Communication Networks

JF - Nano Communication Networks

SN - 1878-7789

ER -